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

Ответ:

Bon2000

15.10.2020 15:07

Докажем тождество $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]$ , что легко доказывается по индукции. Взяв определитель от обеих сторон, приходим к требуемому.

Теперь докажем лемму: для любого четного $\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}}$ (применяя тождество, получаем разницу 1), лемма доказана.

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

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