Proof of Binet’s formula

Where x_n is the nth Fibonacci number, prove that $ \forall n \in \mathbb{N}, x_n = \frac {1}{\sqrt{5}} \left[\left(\frac {1 + \sqrt {5}}{2}\right)^n - \left(\frac {1 - \sqrt {5}}{2}\right)^n\right] $.

To prove the closed‐form (“Binet’s”) formula

$$ x_n \;=\;\frac1{\sqrt5}\Bigl(\phi^n - \psi^n\Bigr), \quad\text{where}\quad \phi = \frac{1 + \sqrt5}2,\quad \psi = \frac{1 - \sqrt5}2, $$

we’ll show that the right‐hand side satisfies

1. the same recurrence as the Fibonacci numbers,
2. the same initial conditions,

and then invoke uniqueness of solutions to a linear recurrence.

---

1. Setup: characteristic equation

The Fibonacci numbers are defined by

$$ x_0 = 0,\quad x_1 = 1,\quad x_n = x_{n-1} + x_{n-2}\quad(\forall n\ge2). $$

The associated characteristic polynomial is

$$ r^2 - r - 1 = 0, $$

whose two roots are

$$ \phi = \tfrac{1+\sqrt5}2, \qquad \psi = \tfrac{1-\sqrt5}2. $$

Since this is a distinct‐root second‐order homogeneous recurrence, its general solution is

$$ a_n \;=\; A\,\phi^n + B\,\psi^n $$

for constants $A,B$ determined by $a_0$ and $a_1$.

---

2. Determine $A$ and $B$ via initial conditions

We want $a_n = x_n$, so impose

1. $a_0 = A + B = x_0 = 0$,
2. $a_1 = A\,\phi + B\,\psi = x_1 = 1$.

From $A+B=0$ we get $B=-A$. Plugging into the second,

$$ A\,\phi - A\,\psi \;=\; 1 \quad\Longrightarrow\quad A(\phi - \psi) = 1. $$

But $\phi - \psi = \sqrt5$, so $A = 1/\sqrt5$ and hence $B = -1/\sqrt5$. Therefore

$$ a_n \;=\;\frac1{\sqrt5}\,\phi^n \;-\;\frac1{\sqrt5}\,\psi^n \;=\;\frac1{\sqrt5}\bigl(\phi^n - \psi^n\bigr). $$

---

3. Check that $a_n$ satisfies the Fibonacci recurrence

Since $\phi$ and $\psi$ are roots of $r^2 = r+1$, we have

$$ \phi^n = \phi^{n-1} + \phi^{n-2}, \quad \psi^n = \psi^{n-1} + \psi^{n-2}. $$

Hence

$$ a_n =\frac{\phi^n - \psi^n}{\sqrt5} =\frac{(\phi^{n-1}+\phi^{n-2}) - (\psi^{n-1}+\psi^{n-2})}{\sqrt5} =\frac{\phi^{n-1}-\psi^{n-1}}{\sqrt5} \;+\;\frac{\phi^{n-2}-\psi^{n-2}}{\sqrt5} =a_{n-1} + a_{n-2}. $$

Thus $a_n$ obeys the same recurrence as $x_n$.

---

4. Conclusion by uniqueness

We have produced a sequence $a_n=(\phi^n-\psi^n)/\sqrt5$ which

• satisfies the same recurrence $a_n = a_{n-1}+a_{n-2}$,
• has the same initial values $a_0=0$, $a_1=1$.

By the standard uniqueness theorem for linear recurrences, it follows that

$$ a_n = x_n \quad\forall n\in\Bbb N. $$

That is,

$$ \boxed{ x_n =\frac1{\sqrt5}\Bigl(\phi^n - \psi^n\Bigr) =\frac1{\sqrt5}\Bigl(\bigl(\tfrac{1+\sqrt5}2\bigr)^n -\bigl(\tfrac{1-\sqrt5}2\bigr)^n\Bigr). } $$

This completes the proof. ∎