Récurrence double et suite de Fibonacci

Notons $\alpha =\frac{1+\sqrt{5}}{2}$ et $\beta =\frac{1-\sqrt{5}}{2}$. Ce sont les racines de l'équation caractéristique $r^2-r-1=0$, donc ${\alpha }^2=\alpha +1$ et ${\beta }^2=\beta +1$. Soit $P(n)$ la propriété : $F_n=\frac{{\alpha }^n-{\beta }^n}{\sqrt{5}}$.

• Initialisation :
• Pour $n=0$ : $\frac{{\alpha }^0-{\beta }^0}{\sqrt{5}}=0=F_0$, donc $P(0)$ est vraie.
• Pour $n=1$ : $\frac{{\alpha }^1-{\beta }^1}{\sqrt{5}}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}\right)=\frac{\sqrt{5}}{\sqrt{5}}=1=F_1$, donc $P(1)$ est vraie.
• Hérédité : Supposons $P(n)$ et $P(n+1)$ vraies pour un certain $n\ge 0$. Calculons $F_{n+2}$ :

$$F_{n+2}=F_{n+1}+F_n=\frac{{\alpha }^{n+1}-{\beta }^{n+1}}{\sqrt{5}}+\frac{{\alpha }^n-{\beta }^n}{\sqrt{5}}$$

$$=\frac{{\alpha }^n(\alpha +1)-{\beta }^n(\beta +1)}{\sqrt{5}}$$

Or $\alpha +1={\alpha }^2$ et $\beta +1={\beta }^2$, d'où :

$$F_{n+2}=\frac{{\alpha }^n\cdot {\alpha }^2-{\beta }^n\cdot {\beta }^2}{\sqrt{5}}=\frac{{\alpha }^{n+2}-{\beta }^{n+2}}{\sqrt{5}}$$

Ainsi $P(n+2)$ est vraie. Par le principe de récurrence double, la formule est établie pour tout $n\in \mathbb{N}$.