Logo
Published on

The Fibonacci Generating Function

Authors
  • avatar
    Name
    Vu Hung
    Twitter

Problem Statement

Let FnF_n be the nn-th Fibonacci number (F1=1,F2=1,Fn=Fn−1+Fn−2F_1=1, F_2=1, F_n = F_{n-1} + F_{n-2}). We define the power series S(x)S(x) as:

S(x)=∑n=1∞Fnxn+1S(x) = \sum_{n=1}^\infty F_n x^{n+1}
  • By expanding S(x)−xS(x)−x2S(x)S(x) - xS(x) - x^2S(x) and using the recurrence property of Fibonacci numbers, prove that:
S(x)=x21−x−x2S(x) = \frac{x^2}{1 - x - x^2}
  • Given the growth rate of Fibonacci numbers, explain why this series converges for x=0.1x = 0.1.
  • Show that S(0.1)=189S(0.1) = \frac{1}{89}.
  • The decimal expansion of 189\frac{1}{89} is 0.011235955…0.011235955\dots. Explain why the digit in the 10−710^{-7} place is 99 rather than the expected Fibonacci number F6=8F_6 = 8.

Hints

Consider the definition of S(x)S(x) term by term for (i). For (iv), look closely at how the next Fibonacci number F7=13F_7=13 interacts with the decimal places.

Solutions

(i) Substitution into S(x)(1−x−x2)S(x)(1-x-x^2) cancels out all terms except the first, leaving F1x2=x2F_1 x^2 = x^2. Hence S(x)=x21−x−x2S(x) = \frac{x^2}{1-x-x^2}.

(ii) Fibonacci numbers grow roughly geometrically by the golden ratio ϕ≈1.618\phi \approx 1.618. Because 1.618⋯×0.1<11.618 \dots \times 0.1 < 1, the series converges.

(iii) Substitute x=0.1x=0.1:

S(0.1)=0.121−0.1−0.12=0.011−0.1−0.01=0.010.89=189.S(0.1) = \frac{0.1^2}{1 - 0.1 - 0.1^2} = \frac{0.01}{1 - 0.1 - 0.01} = \frac{0.01}{0.89} = \frac{1}{89}.

(iv) The required sum gives F6×(0.1)7+F7×(0.1)8F_6 \times (0.1)^7 + F_7 \times (0.1)^8. F6=8F_6 = 8 and F7=13F_7 = 13, so the sum overlapping the 10−710^{-7} place includes the carry-over from F7F_7: 8+1=98 + 1 = 9.

Takeaways

  • Power series generating functions can be explicitly derived using recurrence relations.
  • The decimal expansion of fractions naturally encodes the base-10 carry-over of power series evaluations.
  • Fibonacci recursion can also be visualised geometrically via a quarter-turn spiral whose radii follow consecutive Fibonacci numbers.

% % }

Further Readings

Connect with me