Example: the formula for the Fibonacci sequence

As we worked out earlier, $\{F_n\}$ satisfies a linear recurrence with characteristic polynomial $x^2-x-1$. By the quadratic formula, this factors as $(x-\alpha)(x-\beta)$ where $\alpha=(1+\sqrt{5})/2$ is the golden ratio, and $\beta=(1-\sqrt{5})/2$. The main theorem implies that there are constants $A$ and $B$ such that

$$F_n = A \alpha^n + B \beta^n$$

for all $n$. Using $F_0=0$ and $F_1=1$ we obtain

$$0 = A + B, \qquad 1= A \alpha+B \beta.$$

Solving for $A$ and $B$ yields $A=1/(\alpha-\beta)$ and $B=-1/(\alpha-\beta)$, so

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

for all $n$.