Prueba de inducción: Fórmula de los números de Fibonacci como función par e impar

Question

¿Cómo podemos demostrar por inducción lo siguiente?

$ F_{n+1} = \left\{ \begin{array}{l l} F_{n/2}^2+F_{(n+2)/2}^2 & \quad \text{if $n$ is even}\\ F_{(n-1)/2}F_{(n+1)/2}+F_{(n+1)/2}F_{(n+3)/2} & \quad \text{if $n$ is odd }\\ \end{array} \right. $

Sé que el número par es $2m$ y el número impar es $2m+1$ .

Answer 1

En primer lugar, defina los números de Fibonacci:

Dejemos que $F_n$ sea la secuencia de números de Fibonacci, dada por

$$F_0 = 0, F_1 = 1, \text{ and}\quad F_n = F_{n-1} + F_{n-2}\; \text{ for}\; n \geq 2.$$

Pistas:

$(1)$ Utilice el definición de $F_n$ .

• Por ejemplo, $F_{n+1} = F_{n} + F_{n-1}$

$(2)$ Puedes utilizar las siguientes identidades que te conviene conocer:

i) $F_{n-1}^2 + F_n^2 = F_{2n}$ .

ii) $F_{n-1}F_n + F_n F_{n+1} = F_{2n+1}$ .

Nótese que las identidades anteriores se derivan de la identidad más general :

$(I)$ : Para $n, m \in \mathbb{N}$ : $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$

---

Prueba de $(I)$ :

Fijar $n \in \mathbb{N}$ . Utilizaremos la inducción sobre $m$ . Para $m=1$ la parte derecha de la ecuación se convierte en $$F_{n-1}F_{1} + F_{n}F_{2} = F_{n-1} + F_{n},$$ que es igual a $F_{n+1}$ . Cuando $m=2$ La ecuación también es cierta (¡espero que puedas demostrarlo!).

Supongamos ahora que el resultado es cierto para $k=3,4, \cdots , m$ . Queremos demostrar que el resultado es cierto para $k=m+1$ . $$ \text{For} \ k=m-1 \ \text{we have} \quad F_{n+m-1} = F_{n-1}F_{m-1} + F_{n}F_{m},\,\text{ and}$$ $$ \text{For} \ k = m \ \text{we have} \quad F_{m+n}=F_{n-1}F_{m} + F_{n}F_{m+1}$$ Sumando ambos lados se obtiene $$F_{m+n-1} + F_{m+n} = F_{m+n+1} = F_{n-1}F_{m+1} + F_{n}F_{m+2},$$ $$\text{so,}\;\; F_{m+n}=F_{n-1}F_m + F_{n}F_{m+1}$$

---

Las identidades (i) y (ii) se deducen de $(I)$ poniendo $m = n$ y manipular las expresiones.

---

Answer 2

Haz lo siguiente:

1. Comprueba que se mantiene para el caso base.
2. Supongamos que se cumple para todo <= 2n (probablemente se puede debilitar) .
3. Se tiene entonces que para 2n+1 $$F_{2n+1} = F_{2n}+F_{2n-1} = F^2_n+F^2_{n+1}+F_{n-1}F_{n} +F_nF_{n+1} = F_n(F_n+F_{n-1})+F_{n+1}(F_n+F_{n+1})=F_nF_{n+1}+F_{n+1}F_{n+2}.$$
4. Haz una manipulación similar para 2n+2 , utilizando lo que acabamos de demostrar para 2n+1. Ya has terminado.