Prueba $F_{n+1} ≤ (\frac74)^n $ , donde $F_n$ son números de Fibonacci

Question

Dejemos que $F_n$ sea el $n$ -El número de Fibonacci número 1, definido recursivamente por $F_0 = 0$ , $F_1 = 1$ y $F_n = F_{n1} + F_{n2}$ para $n 2$ .

Demuestra lo siguiente por inducción (o inducción fuerte):

$(a)$ Para todos $n 0$ , $F_{n+1} \left(\dfrac74\right)^n$ .

$(b)$ Dejemos que $G_n$ sea el número de tilings de un $2 × n$ rejilla utilizando piezas de dominó (es decir $2 × 1$ o $1 × 2$ piezas). Entonces demuestre $G_n = F_{n+1}$ .

Para la pregunta $(a)$ He hecho la prueba pero el resultado que obtenía era $$\left(\frac74\right)^{k+1}\left(\frac{11}7\right)\left(\frac74\right)^{k+1}$$ que está mal.

Answer 1

La base es evidente.

Dejemos que $F_{n}\leq\left(\frac{7}{4}\right)^{n-1}$ y $F_{n+1}\leq\left(\frac{7}{4}\right)^{n}$ .

Así, $$F_{n+2}=F_{n+1}+F_n\leq\left(\frac{7}{4}\right)^{n}+\left(\frac{7}{4}\right)^{n-1}$$ y es suficiente para demostrar que $$\left(\frac{7}{4}\right)^{n}+\left(\frac{7}{4}\right)^{n-1}\leq\left(\frac{7}{4}\right)^{n+1}$$ o $$\frac{7}{4}+1\leq\frac{49}{16},$$ que es $44\leq49$ Lo cual es cierto.

$(b)$ es cierto porque por la definición de $G$ obtenemos: $G_{n+2}=G_{n+1}+G_{n}$ , $G_1=1$ y $G_2=2$ .