Recurrence Relations - Key Proof

Binet's formula provides an explicit closed form for Fibonacci numbers, demonstrating how characteristic equation methods yield exact solutions to important recurrence relations.

Proof:

The Fibonacci sequence satisfies $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$ and $F_1 = 1$.

Step 1: Find the characteristic equation.

For the recurrence $F_n - F_{n-1} - F_{n-2} = 0$, the characteristic equation is: $r^2 - r - 1 = 0$

Step 2: Solve for the roots.

Using the quadratic formula: $r = \frac{1 \pm \sqrt{1 + 4}}{2} = \frac{1 \pm \sqrt{5}}{2}$

Let $\phi = \frac{1 + \sqrt{5}}{2}$ and $\hat{\phi} = \frac{1 - \sqrt{5}}{2}$.

Step 3: Write the general solution.

Since we have two distinct real roots, the general solution is: $F_n = A\phi^n + B\hat{\phi}^n$

for some constants $A$ and $B$.

Step 4: Apply initial conditions.

Using $F_0 = 0$: $F_0 = A + B = 0$ So $B = -A$.

Using $F_1 = 1$: $F_1 = A\phi + B\hat{\phi} = A(\phi - \hat{\phi}) = 1$

Now, $\phi - \hat{\phi} = \frac{1 + \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{2} = \sqrt{5}$.

Therefore: $A \cdot \sqrt{5} = 1$, so $A = \frac{1}{\sqrt{5}}$ and $B = -\frac{1}{\sqrt{5}}$.

Step 5: Write the final formula.

$F_n = \frac{1}{\sqrt{5}}\phi^n - \frac{1}{\sqrt{5}}\hat{\phi}^n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}}$

This completes the proof. $\square$

Verification:

Let's verify for small values:

• $F_0 = \frac{\phi^0 - \hat{\phi}^0}{\sqrt{5}} = \frac{1 - 1}{\sqrt{5}} = 0$ ✓
• $F_1 = \frac{\phi - \hat{\phi}}{\sqrt{5}} = \frac{\sqrt{5}}{\sqrt{5}} = 1$ ✓
• $F_2 = \frac{\phi^2 - \hat{\phi}^2}{\sqrt{5}}$

Note that $\phi^2 = \phi + 1$ (since $\phi$ satisfies $r^2 = r + 1$) and similarly $\hat{\phi}^2 = \hat{\phi} + 1$.

So $F_2 = \frac{(\phi + 1) - (\hat{\phi} + 1)}{\sqrt{5}} = \frac{\phi - \hat{\phi}}{\sqrt{5}} = 1$ ✓