натуральные-числа - Числа Фибоначчи

Хотя рекуррентная формула для чисел Фибоначчи общеизвестна, выбор нумерации может немного варьироваться, поэтому полезно было бы уточнить, что в данном случае $%f_1=f_2=1$%.

Воспользуемся формулой Бине (если она не предполагается известной, то её вывод можно легко осуществить): $%f_n=\frac1{\sqrt5}(\lambda_1^n-\lambda_2^n)$%, где $%\lambda_1=\frac{1+\sqrt5}2$%, $%\lambda_2=\frac{1-\sqrt5}2$%. Заметим, что $%\lambda_1+\lambda_2=1$%, $%\lambda_1\lambda_2=-1$%.

Из этой формулы мы имеем $%f_n^2=\frac15(\lambda_1^{2n}+\lambda_2^{2n}-2(-1)^n)$%, а также $%f_{n+r}f_{n-r}=\frac15(\lambda_1^{n+r}-\lambda_2^{n+r})(\lambda_1^{n-r}-\lambda_2^{n-r})=\frac15(\lambda_1^{2n}+\lambda_2^{2n}-(-1)^{n-r}(\lambda_1^{2r}+\lambda_2^{2r}))$% за счёт того, что $%\lambda_1\lambda_2=-1$%. Следовательно, $%f_n^2-f_{n+r}f_{n-r}=\frac15(-1)^{n-r}(\lambda_1^{2r}+\lambda_2^{2r}-2(-1)^r)$%.

Согласно формуле для квадрата $%n$%-го числа Фибоначчи, в которой мы полагаем $%n=r$%, получилось $%(-1)^{n-r}f_r^2$%, что доказывает тождество.