Demostrar por inducción que para los números Fibonacci $F(n)$ con $n \ge 6$, $F(n) \ge 2^{n/2}$

Question

Demuestre por inducción que $F(n) \ge 2^{n/2}$ para $n \ge 6

He realizado los siguientes pasos: 1) Caso base: $F(6) = 8$, $2^{0.5 \cdot 6} = 8$, caso base demostrado.

2) Inducción: asumamos que $F(k) \ge 2^{0.5k}$ es verdadero.

Ahora necesitamos demostrar que $F(k+1) \ge 2^{0.5(k+1)}$ también es verdadero. ¿Algún idea?

Answer 1

Dado que los números de Fibonacci se definen por una ecuación de recurrencia de segundo orden, debes comenzar con dos casos base: $$F(7)=13>\sqrt{2^7}$$

Ahora, para $n\ge 8$, $$F(n+2)=F(n+1)+F(n)\ge\sqrt{2^n}+\sqrt{2^{n+1}}=\sqrt{2^n}(1+\sqrt 2)>2\sqrt{2^{n}}$$

Answer 2

Considere el problema más general: ¿Para qué $a,b>0$ tenemos $F(n) \ge ab^n$ ?

El argumento de inducción natural es el siguiente: $$ F(n+1) = F(n)+F(n-1) \ge ab^n + ab^{n-1} = ab^{n-1}(b+1) $$ Este argumento funcionará si y solo si $b+1 \ge b^2$ (y esto sucede exactamente cuando $b \le \phi$).

Entonces, en su caso, solo tiene que verificar que $b+1 \ge b^2$ para $b=\sqrt 2$, lo que se deduce de $\sqrt 2 \ge 1$.

Esto solo se encarga del paso de inducción. Aún necesita los casos base, $n=N$ y $n=N+1$; diferentes $a,b$ probablemente necesitarán diferentes $N$.