Prueba inductiva de la fórmula cerrada de la sucesión de Fibonacci

Question

Números de Fibonacci $f(n)$ se definen de forma recursiva: $f(n) = f(n-1) +f(n-2)$ para $n > 2$ y $f(1) = 1$ , $f(2) = 1$ .

También admiten una forma cerrada sencilla: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt 5}{2}\right)^n- \left(\dfrac{1 - \sqrt 5}{2}\right)^n \tag1$$

¿Cómo demostrar (1) utilizando la inducción?

Observaciones

Se podría obtener (1) por el método general de resolución de recurrencias: buscar soluciones de la forma $f(n)=r^n$ y luego ajustarlos a los valores iniciales.

Pero debería haber una prueba más concreta para esta secuencia específica, utilizando el principio de inducción matemática.

Answer 1

Me ocuparé sólo del paso inductivo.

Dejemos que $\alpha =\dfrac{1+\sqrt 5}{2}$ y $\beta =\dfrac{1-\sqrt 5}{2}$ .

Tenga en cuenta que $\alpha^2=1+\alpha$ y $\beta ^2=1+\beta$ . Esto es una consecuencia directa del hecho de que $\alpha$ y $\beta$ son raíces de $x^2-x-1$ .

Supongamos que dado $n\in \Bbb N$ tal que $n\ge 3$ se sostiene que $$\tag {I.H.}(\forall k\in \Bbb N)(k<n\implies\sqrt 5f(k)=\alpha^k-\beta ^k)$$

Desde $n\ge 3$ , $f(n)=f(n-2)+f(n-1)$ Por lo tanto $\sqrt 5f(n)=\sqrt 5f(n-2)+\sqrt 5f(n-1)$ y aplicando el $\text{I.H.}$ se deduce que $$\sqrt 5f(n)=\alpha ^{n-2}-\beta ^{n-2}+\alpha ^{n-1}-\beta ^{n-1}=\left(\alpha^{n-2}+\alpha^{n-1}\right)-\left(\beta ^{n-2}+\beta ^{n-1}\right).$$

Ahora, al factorizar adecuadamente, se obtiene $$\sqrt 5f(n)=\alpha ^{n-2}(1+\alpha )-\beta ^{n-2}(1+\beta).$$

Ahora usa $\alpha^2=1+\alpha$ y $\beta ^2=1+\beta$ para concluir.

Answer 2

Así que lo comprobamos:

• Casos base : Mostrar $$\sqrt{5}\ f(1)= \frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}$$ y $$\sqrt{5}\ f(2)= \frac{(1+\sqrt{5})^2}{2}-\frac{(1-\sqrt{5})^2}{2}.$$ Tendrás que comprobar dos casos base ya que la recurrencia tiene profundidad $2$ .

• Paso inductivo : Supongamos que $$\sqrt{5}\ f(k)= \frac{(1+\sqrt{5})^k}{2^k}-\frac{(1-\sqrt{5})^k}{2^k}$$ para todos $1 \leq k \leq N$ . Utilice esto para deducir que $$\sqrt{5}\ f(N+1)= \frac{(1+\sqrt{5})^{N+1}}{2^{N+1}}-\frac{(1-\sqrt{5})^{N+1}}{2^{N+1}}.$$

  La forma de hacerlo es sacar términos que se parezcan a la fórmula anterior de $\sqrt{5}\ f(N)$ . Debería ser posible manipular la fórmula para obtener $\sqrt{5}\ f(N)+\sqrt{5}\ f(N-1)$ , a continuación, utilice el hipótesis inductiva .

• Concluya, por inducción, que la fórmula es válida para todo $n \geq 1$ .

Tenga en cuenta que esto se conoce como Fórmula de Binet para el Números de Fibonacci .