TheoremProved

Partial fractions give Binet's formula

Statement

With $\varphi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}$ , the roots of $1-x-x^2$ give the closed form $F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right)$ for every $n\ge0$ .

Why is it true?

Every rational generating function with distinct linear factors in its denominator splits into a sum of simple geometric series, and each geometric series is read off directly as an explicit formula for the coefficient.

Proof sketch

Factor the denominator: since the roots of $1-x-x^2=0$ are $x=1/\varphi$ and $x=1/\psi$ , we have $1-x-x^2=(1-\varphi x)(1-\psi x)$ .

Write $\frac{x}{1-x-x^2}=\frac{A}{1-\varphi x}+\frac{B}{1-\psi x}$ for constants $A,B$ . Clearing denominators and matching the constant term and the coefficient of $x$ gives a linear system whose solution is $A=\frac{1}{\sqrt5}$ , $B=-\frac{1}{\sqrt5}$ , so $\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\varphi x}-\frac{1}{1-\psi x}\right)$ .

Expand each term as a geometric series: $\frac{1}{1-\varphi x}=\sum_{n\ge0}\varphi^nx^n$ and $\frac{1}{1-\psi x}=\sum_{n\ge0}\psi^nx^n$ .

Reading off the coefficient of $x^n$ on both sides gives $F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right)$ , known as Binet's formula.

Topics that use this theorem

Generating functions

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Herbert S. Wilf (1994). generatingfunctionology
Philippe Flajolet, Robert Sedgewick (2009). Analytic Combinatorics