Question

Числа F0, F1, F2,... заданы так: F0=0, F1=1, Fn+2=Fn+1+Fn для n=0,1,2
Докажите, что для каждого n большего или равного 0 подходит:
Fn меньше/равно ((1+ корень из 5)/2)в степени n-1

Answer 1

Докажем тождество $F_{n+1}F_{n-1}-F_{n}^2=(-1)^n$. Для этого заметим, что $\left[\begin{array}{cc}1&1\\1&0&\end{array}\right]^n= \left[\begin{array}{cc}F_{n+1}&F_{n}\\F{n}&F_{n-1}&\end{array}\right]$, что легко доказывается по индукции. Взяв определитель от обеих сторон, приходим к требуемому.

Теперь докажем лемму: для любого четного $n$ $\frac{F_{n+1}}{F_{n}} < \frac{1+\sqrt{5}}{2}$.

Доказательство: пусть $a_{n}=\frac{F_{n}}{F_{n+1}}$. Сразу примем, что предел этой последовательности существует. Это равносильно $\lim\limits_{n\to\infty}(a_{n}-a_{n-1})=0$.$a_{n}-a_{n-1}=\frac{F_{n}}{F_{n+1}}-\frac{F_{n-1}}{F_{n}}=\frac{F_{n}^2-F_{n+1}F_{n-1}}{F_{n+1}F_{n}}=\frac{(-1)^{n+1}}{F_{n+1}F_{n}}$. Отсюда очевидно, что $\lim\limits_{n\to\infty}(a_{n}-a_{n-1})=0$. Пусть $L=\lim\limits_{n\to\infty}a_{n}$. Тогда $\frac{F_{n+1}}{F_{n}}=\frac{F_{n}+F_{n-1}}{F_{n}}=1+\frac{F_{n-1}}{F_{n}}$. Взяв предел от обеих частей, приходим к $\frac{1}{L}=1+L \Rightarrow L=\frac{1+\sqrt{5}}{2}$.  Поскольку $\frac{F_{n+1}}{F_{n}}<\frac{F_{n+2}}{F_{n+1}}$ (применяя тождество, получаем разницу 1), лемма доказана.

Теперь по индукции.

База $k=0$ очевидна. Пусть для всех $n\leq k$ это верно. Докажем, что $F_{k+1}\leq (\frac{1+\sqrt{5}}{2})^k$ . Пусть $k$ четно, тогда $\frac{F_{k+1}}{F_{k}}\leq \frac{1+\sqrt{5}}{2}$, домножая на $F_{k}$ и применяя предположение индукции, получаем требуемое. Теперь неравенство выполняется для всех $n\leq k+1$. Далее берем $k+2$ — четное число — и повторяем операцию. Тем самым докажем для всех нечетных чисел.

Теперь докажем для всех четных. $F_{k+2}=F_{k+1}+F_{k}\leq \varphi^k+\varphi^{k-1}=\varphi^k(1+\varphi^{-1})=\varphi^{k+1}$, что и требовалось