Proof of Binet's formula by induction

Proof

We argue by induction on $n$, for two consecutive terms at a time.

1. Let $\varphi = \frac{1 + \sqrt{5}}{2}$ and $\psi = \frac{1 - \sqrt{5}}{2}$. For a natural number $n$, let $G_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$.
2. By the description of the golden ratio, $\varphi$ and $\psi$ are the roots of $x^2 - x - 1$. So $\varphi^2 = \varphi + 1$ and $\psi^2 = \psi + 1$.
3. Directly, $\psi^2 = \frac{1 - 2\sqrt{5} + 5}{4} = \frac{3 - \sqrt{5}}{2} = \psi + 1$, and the same computation with $+\sqrt{5}$ checks $\varphi^2 = \varphi + 1$.
4. We have $G_0 = \frac{1 - 1}{\sqrt{5}} = 0$ and $G_1 = \frac{\varphi - \psi}{\sqrt{5}} = \frac{\sqrt{5}}{\sqrt{5}} = 1$.
5. For every natural number $n$, step 2 gives $\varphi^{n+2} = \varphi^{n+1} + \varphi^n$ and $\psi^{n+2} = \psi^{n+1} + \psi^n$. Subtracting and dividing by $\sqrt{5}$ gives $G_{n+2} = G_{n+1} + G_n$.
6. Let $P(n)$ be the claim that $G_n = F_n$ and $G_{n+1} = F_{n+1}$, where $F_m$ are the Fibonacci numbers.
7. $P(0)$ holds by step 4, since $F_0 = 0$ and $F_1 = 1$.
8. Assume $P(n)$. Then $G_{n+1} = F_{n+1}$, and by step 5, $G_{n+2} = G_{n+1} + G_n = F_{n+1} + F_n = F_{n+2}$. So $P(n + 1)$ holds.
9. By induction, $P(n)$ holds for every natural number $n$. In particular $F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$ for every $n$.