Indukcja, aby udowodnić, że sekwencja Fibonacciego rośnie wykładniczo szybko [duplikat]

Question

Jak rozwiązać ten problem za pomocą indukcji?

Użyj indukcji, aby to udowodnić

$F_n\ge2^{\frac n2}\;,\;$ dla $n\ge6\;.$

$F_0=0\;,\;F_1=1\;,\;F_n=F_{n-1}+F_{n-2}\;.$

Answer 1

Każdy problem z indukcją można rozwiązać w trzech krokach.

Krok 1, udowodnij swoje podstawowe przypadki. W takim przypadku należy najpierw pokazać , że$F(n)\geq 2^\frac n2$ gdy $n=6$ (to znaczy $F(6)\geq 2^3=8$). Ćwiczenia$F(6)$tutaj wystarczy. Ponieważ definicja rekurencyjna jest oparta na dwóch wcześniejszych przypadkach ($F(n)=F(n-1)+F(n-2)$, na prawej stronie znajdują się dwa terminy), potrzebny jest również drugi przypadek podstawowy, następny dalej $n=7$, więc pokaż to $F(7)\geq 2^\frac 72$ (Podpowiedź: podnieś tę liczbę do kwadratu, aby znaleźć przybliżoną wartość liczbową)

Krok 2, Załóżmy, że właściwość jest prawdziwa dla danego $k,k+1$. To znaczy załóżmy$F(k)\geq 2^\frac k2, F(k+1)\geq 2^{\frac{k+1}{2}}\tag1$

Krok 3: Użyj tego, aby udowodnić, że stwierdzenie jest prawdziwe w następnym przypadku, tj $(1)$ wynika z tego $$F(k+2)=F(k+1)+F(k)\geq 2^{\frac{k+2}{2}}$$

Answer 2

$F_6=8\ge2^{\frac62}\;.$

$F_7=13\ge\sqrt{2^7}=2^{\frac72}\;.$

Teraz dla $\;n\ge8\;,$ przypuszczamy, że $\;F_{n-2}\ge2^\frac{n-2}{2},\;F_{n-1}\ge2^\frac{n-1}{2}$ i udowodnij to $\;F_n\ge2^\frac n2.$

$F_n=F_{n-1}+F_{n-2}\ge2^{\frac{n-1}{2}}+2^{\frac{n-2}{2}}=2^{\frac{n-2}{2}}\big(\sqrt 2+1\big)\ge$

$\ge2^{\frac n2-1}\cdot 2=2^{\frac n2}.$

Stąd przez indukcję $n$, wynika, że

$F_n\ge2^\frac n2\quad$ dla wszystkich $\;n\ge6\;.$