Proof of Binet’s formula for the Fibonacci sequence

Briefly define the Fibonacci sequence.

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. It begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Mathematically, it's defined as:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n ≥ 2.

Prove that, ∀n∈ℕ, $F(n) = \frac {1}{\sqrt{5}} \left[\left(\frac {1 + \sqrt {5}}{2}\right)^n - \left(\frac {1 - \sqrt {5}}{2}\right)^n\right]$.

We are asked to prove Binet’s formula for the Fibonacci sequence:

$$ F(n) = \frac{1}{\sqrt{5}} \left[\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n\right], \quad \forall n \in \mathbb{N} $$

---

Step 1: Define the Fibonacci recurrence

The Fibonacci sequence is defined as:

• $F(0) = 0$
• $F(1) = 1$
• $F(n) = F(n-1) + F(n-2)$, for $n \geq 2$

---

Step 2: Use recurrence relation approach with characteristic equation

Assume a solution of the form:

$$ F(n) = A\alpha^n + B\beta^n $$

where $\alpha$ and $\beta$ are the roots of the characteristic equation derived from the recurrence:

$$ x^2 = x + 1 \Rightarrow x^2 - x - 1 = 0 $$

Solving this quadratic:

$$ \alpha = \frac{1 + \sqrt{5}}{2}, \quad \beta = \frac{1 - \sqrt{5}}{2} $$

So the general solution becomes:

$$ F(n) = A\alpha^n + B\beta^n $$

---

Step 3: Solve for constants $A$ and $B$

Using initial conditions:

For $n = 0$:

$$ F(0) = A\alpha^0 + B\beta^0 = A + B = 0 \Rightarrow B = -A $$

For $n = 1$:

$$ F(1) = A\alpha + B\beta = A\alpha - A\beta = A(\alpha - \beta) = 1 $$

We calculate $\alpha - \beta$:

$$ \alpha - \beta = \frac{1 + \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{2} = \frac{2\sqrt{5}}{2} = \sqrt{5} $$

So:

$$ A(\sqrt{5}) = 1 \Rightarrow A = \frac{1}{\sqrt{5}}, \quad B = -\frac{1}{\sqrt{5}} $$

---

Step 4: Final formula

Substitute $A$ and $B$ back into the general solution:

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

---

✅ Conclusion

We have proven that:

$$ \boxed{F(n) = \frac {1}{\sqrt{5}} \left[\left(\frac {1 + \sqrt {5}}{2}\right)^n - \left(\frac {1 - \sqrt {5}}{2}\right)^n\right]} $$

holds for all $n \in \mathbb{N}$.