THE GENERATING FUNCTION FOR THE FIBONACCI SEQUENCE

Mohammad K. Azarian University of Evansville

\underline{Definition}. Let a_{0}, a_{1}, a_{2}, …, be a sequence of real numbers. The function

f(x) = a_{0} + a_{1}x + a_{2}x^{2} + ⋯ = ∑_{i=0}^{∞} a_{i}x^{i}

is called the \underline{generating function} for the given sequence.

Let F_{n} (n ≥ 1) represent the general term of the Fibonacci sequence

1, 1, 2, 3, 5, 8, 13, ….

The generating function for this sequence is

∑_{n=1}^{∞} F_{n}x^{n},

and it is well–known that

(1)  \frac{x}{1 − x − x^{2}} = ∑_{n=1}^{∞} F_{n}x^{n} .

In [1, p. 1] it has been stated that (1) can be verified by long division. But, the method of long division is a long process, especially for large n. The purpose of this note is to verify (1) by the method of generating functions which is quicker, regardless of the value of n.

Now, from the fact that

\frac{1}{1 − ax} = 1 + ax + a^{2}x^{2} + ⋯ + a^{n}x^{n} + ⋯,

we deduce that the coefficient of x^{n} in

\frac{x}{1 − x − x^{2}} = \frac{1}{\sqrt{5}}(\frac{1}{1 − (\frac{1+\sqrt{5}}{2})x} − \frac{1}{1 − (\frac{1−\sqrt{5}}{2})x})

is

A_{n} = \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^{n} − (\frac{1 − \sqrt{5}}{2})^{n}) , n ≥ 1 .

But, if F_{n} represents the solution to the recurrence relation

F_{n+1} = F_{n} + F_{n−1} , F_{1} = F_{2} = 1, n ≥ 1 ,

for the Fibonacci sequence, then clearly F_{n} = A_{n}.

\underline{Reference}

1. M. Bicknell and V. E. Hoggatt, Fibonacci’s Problem Book, The Fibonacci Association, San Jose State University, San Jose, California, 1974.