Demostración por inducción para una función recursiva $F(n) = F(n–1)+F(n–2)$

Question

Tengo muchos problemas con la siguiente pregunta de deberes:

Considera la siguiente función recursiva:

Caso base: $F(0) = 0,F(1) = 1$ .

Paso recursivo: $F(n)=F(n1)+F(n2)$ para todos $n2$ .

Demostrar que $F(n)\le \left ( \cfrac{1+ \sqrt5}{2} \right) ^{n-1}$

He intentado hacer el paso de inducción reescribiendo esto como $F(k+1) = F(k) + F(k-1)$ y luego subyugando las desigualdades para cada una de $F(k)$ y $F(k-1)$ pero creo que estoy ladrando al árbol equivocado.

Answer 1

Pista: $\displaystyle \frac{1+\sqrt{5}}{2}+1= \frac{3+\sqrt{5}}{2}=(\frac{1+\sqrt{5}}{2})^2$

Lo anterior implica que,

$$\displaystyle F(k+1)=F(k)+F(k-1)\le(\frac{1+\sqrt{5}}{2})^{k-1}+(\frac{1+\sqrt{5}}{2})^{k-2} \text{ (By induction hypothesis)}$$

$$\displaystyle \Rightarrow (\frac{1+\sqrt{5}}{2})^{k-1}+(\frac{1+\sqrt{5}}{2})^{k-2}\le (\frac{1+\sqrt{5}}{2})^{k-2}(\frac{1+\sqrt{5}}{2}+1)\le (\frac{1+\sqrt{5}}{2})^{k-2}(\frac{1+\sqrt{5}}{2})^{2}=(\frac{1+\sqrt{5}}{2})^{k} \text{ (Using Hint)}$$

Answer 2

Pista: La cantidad $\dfrac{1+\sqrt5}2$ es uno de los ceros de $p(x) = x^2-x-1$ . ¿Qué significa esto para la suma de las dos estimaciones?

Answer 3

Visitado conceptualmente, la prueba se vuelve completamente obvia. Sea $\rm\,w = (1\!+\!\sqrt{5})/2.\:$ Observe que ambos $\rm\,F(n)\,$ y $\rm\:G(n) = w^{n-1}$ son soluciones de la recurrencia $\rm\,f(n) = f(n\!-\!1) + f(n\!-\!2)\:$ desde $\rm\: w^{n-1}\!+w^{n-2}\! = w^{n-2}(w\!+\!1) = w^n\,$ por $\rm\:w^2\! = w+1.\:$ Tenemos que demostrar $\rm\:G(n)\ge F(n),\:$ es decir $\rm\: H(n) = G(n)-F(n)\ge 0.\:$ $\rm\,H(n)\,$ también satisface la recurrencia, por lo que un obvio la prueba de inducción lo demuestra: $ $ si $\rm\:H\:$ comienza $\ge 0,\,$ es decir $\rm\:H(0),H(1)\ge 0,\:$ entonces $\rm\,H\,$ permanece $\rm\:\ge 0,\:$ es decir $\rm\:H(n)\ge 0\:$ para todos $\rm\:n\ge 0,\,$

desde $\rm\ \ H(n\!-\!2),\ H(n\!-\!1)\ge 0\ \ \Rightarrow\ \ H(n) = H(n\!-\!2)+H(n\!-\!1) \ge 0 $

La prueba inductiva funciona porque la relación de recursión es una aumentando función de los valores a priori. Por tanto, cualquier solución cuyos valores iniciales sean $\ge 0$ es aumentando para $\rm\,n\ge 2,\:$ así que $\rm\:f(n)\ge f(1)\ge 0.$