フィボナッチ数列が指数関数的に速く成長することを証明するための帰納[重複]

Question

誘導を使用してこれを解決する方法は？

帰納法を使用してそれを証明する

$F_n\ge2^{\frac n2}\;,\;$ にとって $n\ge6\;.$

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

Answer 1

帰納法の問題には3つのステップがあります。

ステップ1、ベースケースを証明します。この場合、最初に表示されていること$F(n)\geq 2^\frac n2$ いつ $n=6$ （すなわち $F(6)\geq 2^3=8$）。ワークアウト$F(6)$ここで十分です。再帰的定義は2つの以前のケースに基づいているため（$F(n)=F(n-1)+F(n-2)$、RHSには2つの用語があります）、2番目のベースケースも必要です。次のケースに沿って、ここでは $n=7$、だからそれを示す $F(7)\geq 2^\frac 72$ （ヒント：この数値を2乗して、おおよその数値を見つけます）

ステップ2、プロパティが特定の場合に当てはまると仮定します $k,k+1$。つまり、$F(k)\geq 2^\frac k2, F(k+1)\geq 2^{\frac{k+1}{2}}\tag1$

ステップ3：これを使用して、ステートメントが次のケースに当てはまることを証明します。 $(1)$ ことを意味します $$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}\;.$

さて、 $\;n\ge8\;,$ 私たちはそれを仮定します $\;F_{n-2}\ge2^\frac{n-2}{2},\;F_{n-1}\ge2^\frac{n-1}{2}$ そしてそれを証明する $\;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}.$

したがって、帰納法によって $n$、それはそれに続く

$F_n\ge2^\frac n2\quad$ すべてのために $\;n\ge6\;.$