Use la recursividad para demostrar los límites de los números de Fibonacci cuando n≥2n≥2n\geq 2

Usar recursividad significa que necesita usar la definición recursiva de$F_n$, ese es el código dado. La prueba en sí es solo una variante de la inducción fuerte: necesita probar dos casos base, porque el siguiente$k$-desigualdad utiliza las dos desigualdades anteriores.

Esto es fácil de ver por$n=2$y$n=3$.

Supongamos que las desigualdades son verdaderas para todos$2\leq k \leq n+1$. Entonces usa eso$F_{n+2}=F_{n+1}+F_n$y sumamos las dos desigualdades$2^{n+1}\geq F_{n+1}\geq 2^\frac{n+1}{2}$y$2^n\geq F_n\geq 2^\frac{n}{2}$para obtener

$$2^{n+2}=4\cdot 2^n\geq3\cdot 2^n =2^n+2^{n+1}\geq F_{n+2}\geq 2^\frac{n}{2}+2^\frac{n+1}{2}=(1+\sqrt{2})2^\frac{n}{2}\geq 2\cdot 2^\frac{n}{2}= 2^\frac{n+2}{2}$$

Límite inferior.

Suponer$F_n > a^n$y$F_{n+1} > a^{n+1}$. Queremos ver en qué condición$a$implicará$F_{n+2} > a^{n+2}$.

$F_{n+2} =F_{n+1}+F_n \gt a^{n+1}+a^n =a^n(a+1)$. Esto es$\gt a^{n+2}$si$a^n(a+1) > a^{n+2}$o$a+1 > a^2$o$\frac54 > a^2-a+\frac14 =(a-\frac12)^2$o$a < \frac{\sqrt{5}}{2}+\frac12 \approx 1.618$.

Desde$\sqrt{2} \approx 1.414 \lt 1.618$, usando$a = \sqrt{2}$y$(\sqrt{2})^n =2^{n/2}$da el límite inferior una vez que lo hemos mostrado durante dos$F_n$.

Esto es casi exactamente lo mismo para el límite superior.

Suponer$F_n < a^n$y$F_{n+1} < a^{n+1}$. Queremos ver en qué condición$a$implicará$F_{n+2} < a^{n+2}$.

Haciendo exactamente el mismo análisis, encontramos que la condición es$a > \frac{\sqrt{5}}{2}+\frac12 \approx 1.618$.

Desde$2 > 1.618$, esto da el límite superior.

Todo lo que queda es mostrar que los límites se mantienen durante dos$F_n$.

Para mostrar analíticamente las desigualdades:

$\begin{array}\\ \sqrt{2} < \frac{\sqrt{5}}{2}+\frac12\\ \iff 2\sqrt{2} < \sqrt{5}+1\\ \iff 8 < (\sqrt{5}+1)^2 =6+2\sqrt{5}\\ \iff 1 < \sqrt{5}\\ \text{which is true.}\\ \end{array}$

$\begin{array}\\ 2 > \frac{\sqrt{5}}{2}+\frac12\\ \iff 3 > \sqrt{5}\\ \iff 9 > 5\\ \text{which is true.}\\ \end{array}$

Usa la inducción...

$n=2$:$2^2\ge2\ge2^{\frac 22}$

Asumir cierto para$k\le n$..

$n+1$:$F_{n+1}=F_n+F_{n-1}$Entonces

$$2^{n+1}\gt3(2^{n-1})=2^n+2^{n-1}\ge F_{n+1}\ge2^{\frac n2}+2^{\frac {n-1}2}=2^{\frac {n-1}2}(2^{\frac12}+1).\ge2^{\frac {n-1}2}\cdot2=2^{\frac {n+1}2}$$ ........