The Fibonacci Generating Function

Generating functions are a powerful bridge between sequences and algebra, turning a recurrence like the Fibonacci rule into a compact rational expression. This topic sits at the intersection of series work from the Advanced course and the more formal power‑series ideas in Extension 1 or Extension 2. By working through the problem below you will see how a simple manipulation of series can unlock a closed form, and you will discover why the fraction (\frac{1}{89}) hides the Fibonacci numbers in its decimal digits.

Problem Statement

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

$$S(x) = \sum_{n=1}^\infty F_n x^{n+1}$$

• By expanding (S(x) - xS(x) - x^2S(x)) and using the recurrence property of Fibonacci numbers, prove that:

$$S(x) = \frac{x^2}{1 - x - x^2}$$

• Given the growth rate of Fibonacci numbers, explain why this series converges for (x = 0.1).
• Show that (S(0.1) = \frac{1}{89}).
• The decimal expansion of (\frac{1}{89}) is (0.011235955\dots). Explain why the digit in the (10^{-7}) place is (9) rather than the expected Fibonacci number (F_6 = 8).

---

Hints

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

---

Solutions

We begin by writing out the three series explicitly and subtracting them. Because the Fibonacci recurrence ties each term to the two before it, the bulk of the expansion cancels, leaving only the very first term.

(i) Substitution into (S(x)(1-x-x^2)) cancels out all terms except the first, leaving (F_1 x^2 = x^2). Hence (S(x) = \frac{x^2}{1-x-x^2}).

For part (ii) we use the known growth of Fibonacci numbers to judge convergence, just as we would for a geometric series. The coefficients behave like (\phi^n), so the series is essentially a geometric series with ratio (\phi x).

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

Now that we have a simple rational form for (S(x)), evaluating it at (x=0.1) is straightforward algebra.

(iii) Substitute (x=0.1):

$$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}.$$

The decimal expansion of (S(0.1)) places each Fibonacci number at a successive power of ten, but once the numbers have two or more digits they cause carries into the higher decimal places. That is exactly what happens for the (10^{-7}) digit — we must consider the overlap with the next term.

(iv) The term involving (F_6) sits at ((0.1)^7) and the term for (F_7) sits at ((0.1)^8). Their combined contribution is (F_6 \times (0.1)^7 + F_7 \times (0.1)^8). With (F_6 = 8) and (F_7 = 13), the sum overlapping the (10^{-7}) place includes the carry-over from the tens digit of (F_7): (8 + 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.
• The Fibonacci recurrence can be visualised geometrically, for example in a quarter-turn spiral where consecutive radii follow Fibonacci numbers.

---

Further Readings

HSC Polynomials, HSC Distributions, HSC Combinatorics, HSC Inequalities