Inducción para demostrar que la secuencia de Fibonacci crece exponencialmente rápido [duplicado]

Nov 27 2020

¿Cómo resolver esto usando inducción?

Usa la inducción para demostrar que

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

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

Respuestas

RhysHughes Nov 27 2020 at 22:29

Hay tres pasos para cualquier problema de inducción.

Paso 1, pruebe sus casos base. En este caso, primero demuestre que$F(n)\geq 2^\frac n2$ cuando $n=6$ (es decir $F(6)\geq 2^3=8$). Haciendo ejercicio$F(6)$basta aquí. Dado que la definición recursiva se basa en dos casos anteriores ($F(n)=F(n-1)+F(n-2)$, hay dos términos en el RHS), también necesita un segundo caso base, el siguiente, aquí es $n=7$, entonces muestra eso $F(7)\geq 2^\frac 72$ (Sugerencia: cuadre este número para encontrar su valor numérico aproximado)

Paso 2, suponga que la propiedad es cierta para un determinado $k,k+1$. Es decir, asumir$F(k)\geq 2^\frac k2, F(k+1)\geq 2^{\frac{k+1}{2}}\tag1$

Paso 3: Use esto para probar que la declaración es válida para el siguiente caso, es decir, que $(1)$ implica que $$F(k+2)=F(k+1)+F(k)\geq 2^{\frac{k+2}{2}}$$

Angelo Nov 27 2020 at 22:37

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

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

Ahora para $\;n\ge8\;,$ suponemos que $\;F_{n-2}\ge2^\frac{n-2}{2},\;F_{n-1}\ge2^\frac{n-1}{2}$ y probar eso $\;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}.$

Por lo tanto, por inducción en $n$, resulta que

$F_n\ge2^\frac n2\quad$ para todos $\;n\ge6\;.$