MathLabs
TheoremProved

Closed form for the Fibonacci generating function

Statement

Let F0=0, F1=1F_0=0,\ F_1=1 and Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} for n≥2n\ge2. Then the ordinary generating function F(x)=∑n=0∞FnxnF(x)=\sum_{n=0}^{\infty}F_nx^n equals F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2}.

Why is it true?

A linear recurrence with constant coefficients always turns into a simple algebraic (in fact, rational) equation once you multiply through by xxn^n and sum over all nn — the recurrence becomes multiplication by a polynomial in xx.

Proof sketch

Multiply the recurrence Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} (valid for n≥2n\ge2) by xnx^n and sum over n≥2n\ge2: ∑n≥2Fnxn=∑n≥2Fn−1xn+∑n≥2Fn−2xn\sum_{n\ge2}F_nx^n=\sum_{n\ge2}F_{n-1}x^n+\sum_{n\ge2}F_{n-2}x^n.

The left side is F(x)−F0−F1x=F(x)−xF(x)-F_0-F_1x=F(x)-x. The first sum on the right is x∑n≥2Fn−1xn−1=x∑m≥1Fmxm=x(F(x)−F0)=xF(x)x\sum_{n\ge2}F_{n-1}x^{n-1}=x\sum_{m\ge1}F_mx^m=x(F(x)-F_0)=xF(x). The second sum is x2∑n≥2Fn−2xn−2=x2∑k≥0Fkxk=x2F(x)x^2\sum_{n\ge2}F_{n-2}x^{n-2}=x^2\sum_{k\ge0}F_kx^k=x^2F(x).

So F(x)−x=xF(x)+x2F(x)F(x)-x=xF(x)+x^2F(x), i.e. (1−x−x2)F(x)=x(1-x-x^2)F(x)=x.

Solving for F(x)F(x) gives F(x)(1−x−x2)=xF(x)(1-x-x^2)=x, hence F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2}, a single rational function that packs the entire infinite Fibonacci sequence.

Topics that use this theorem

Generating functions

Step-by-step proofs

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

References

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