Induction pour prouver que la séquence de Fibonacci croît exponentiellement rapidement [dupliquer]

Question

Comment résoudre ce problème en utilisant l'induction?

Utilisez l'induction pour prouver que

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

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

Answer 1

Il y a trois étapes à tout problème d'induction.

Étape 1, prouvez vos cas de base. Dans ce cas, montrez d' abord que$F(n)\geq 2^\frac n2$ quand $n=6$ (c'est à dire $F(6)\geq 2^3=8$). S'entraîner$F(6)$suffit ici. Puisque la définition récursive est basée sur deux cas antérieurs ($F(n)=F(n-1)+F(n-2)$, il y a deux termes sur le RHS), vous avez également besoin d'un deuxième cas de base, le suivant, ici c'est $n=7$, alors montrez que $F(7)\geq 2^\frac 72$ (Astuce: mettez ce nombre au carré pour trouver sa valeur numérique approximative)

Étape 2, supposons que la propriété est vraie pour un $k,k+1$. Autrement dit, supposons$F(k)\geq 2^\frac k2, F(k+1)\geq 2^{\frac{k+1}{2}}\tag1$

Étape 3: Utilisez ceci pour prouver que l'instruction est valable pour le cas suivant, c'est-à-dire que $(1)$ implique que $$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}\;.$

Maintenant pour $\;n\ge8\;,$ nous supposons que $\;F_{n-2}\ge2^\frac{n-2}{2},\;F_{n-1}\ge2^\frac{n-1}{2}$ et prouve que $\;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}.$

Par conséquent, par récurrence sur $n$, il s'ensuit que

$F_n\ge2^\frac n2\quad$ pour tous $\;n\ge6\;.$