Skip to main content
Mathematics LibreTexts

4.3: Generating Functions and Recurrence Relations

  • Page ID
    6112
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Recall that a recurrence relation for a sequence \(a_{n}\) expresses \(a_{n}\) in terms of values \(a_{i}\) for \(i < n\). For example, the equation \(a_{i} = 3a_{i}−1+2^{i}\) is a first order linear constant coefficient recurrence.

    4.3.1: How Generating Functions are Relevant

    Algebraic manipulations with generating functions can sometimes reveal the solutions to a recurrence relation.

    \(\bullet\) Exercise \(211\)

    Suppose that \(a_i = 3a_{i−1} + 3^i\).

    a. Multiply both sides by \(x^i\) and sum both the left hand side and right hand side from \(i = 1\) to infinity. In the left-hand side, use the fact that

    \[\sum_{i=1}^{\infty}a_ix^i = \left( \sum_{i=0}^{\infty} x^i \right) - a_0 \]

    and in the right hand side, use the fact that

    \[\sum_{i=1}^{\infty}a_{i-1}x^i = x \sum_{i=1}^{\infty}a_ix^{i-1} = x \sum_{j=0}^{\infty} a_j x^j = x \sum_{i=0}^{\infty} a_ix^i \]

    (where we substituted \(j\) for \(i−1\) to see explicitly how to change the limits of summation, a surprisingly useful trick) to rewrite the equation in terms of the power series \(\sum^{∞}_{i=0} a_ix^i\). Solve the resulting equation for the power series \(\sum^{∞}_{i=0} a_ix^i\). You can save a lot of writing by using a variable like y to stand for the power series.

    b. Use the previous part to get a formula for \(a_i\) in terms of \(a_0\).

    c. Now suppose that \(a_i = 3a_{i−1} + 2^i\). Repeat the previous two steps for this recurrence relation. (There is a way to do this part using what you already know. Later on we shall introduce yet another way to deal with the kind of generating function that arises here.) (Hint).

    \(\circ\) Exercise \(212\)

    Suppose we deposit \($5000\) in a savings certificate that pays ten percent interest and also participate in a program to add \($1000\) to the certificate at the end of each year (from the end of the first year on) that follows (also subject to interest.) Assuming we make the \($5000\) deposit at the end of year \(0\), and letting \(a_i\) be the amount of money in the account at the end of year \(i\), write a recurrence for the amount of money the certificate is worth at the end of year \(n\). Solve this recurrence. How much money do we have in the account (after our year-end deposit) at the end of ten years? At the end of \(20\) years?

    4.3.2: Fibonacci Numbers

    The sequence of problems that follows (culminating in Problem 222) describes a number of hypotheses we might make about a fictional population of rabbits. We use the example of a rabbit population for historic reasons; our goal is a classical sequence of numbers called Fibonacci numbers. When Fibonacci1 introduced them, he did so with a fictional population of rabbits.

    4.3.3: Second Order Linear Recurrence Relations

    \(\bullet\) Exercise \(213\)

    Suppose we start (at the end of month \(0\)) with \(10\) pairs of baby rabbits, and that after baby rabbits mature for one month they begin to reproduce, with each pair producing two new pairs at the end of each month afterwards. Suppose further that over the time we observe the rabbits, none die. Let \(a_n\) be the number of rabbits we have at the end of month \(n\). Show that \(a_n = a_{n−1}+2a_{n−2}\). This is an example of a second order linear recurrence with constant coefficients. Using a method similar to that of Problem 211, show that

    \[\sum_{i=0}^{\infty} a_i x^i = \dfrac{10}{1-x-2x^2} \]

    This gives us the generating function for the sequence \(a_i\) giving the population in month \(i\); shortly we shall see a method for converting this to a solution to the recurrence.

    \(\bullet\) Exercise \(214\)

    In Fibonacci’s original problem, each pair of mature rabbits produces one new pair at the end of each month, but otherwise the situation is the same as in Problem 213. Assuming that we start with one pair of baby rabbits (at the end of month \(0\)), find the generating function for the number of pairs of rabbits we have at the end on \(n\) months. (Hint).

    \(\rightarrow\) Exercise \(215\)

    Find the generating function for the solutions to the recurrence \(a_i = 5a_{i−1} − 6a_{i−2} + 2^i\).

    The recurrence relations we have seen in this section are called second order because they specify ai in terms of \(a_{i−1}\) and \(a_{i−2}\), they are called linear because \(a_{i−1}\) and \(a_{i−2}\) each appear to the first power, and they are called constant coefficient recurrences because the coefficients in front of \(a_{i−1}\) and \(a_{i−2}\) are constants.

    4.3.4: Partial Fractions

    The generating functions you found in the previous section all can be expressed in terms of the reciprocal of a quadratic polynomial. However, without a power series representation, the generating function doesn’t tell us what the sequence is. It turns out that whenever you can factor a polynomial into linear factors (and over the complex numbers such a factorization always exists) you can use that factorization to express the reciprocal in terms of power series.

    \(\bullet\) Exercise \(216\)

    Express \(\dfrac{1}{x−3} + \dfrac{2}{x−2}\) as a single fraction.

    \(\circ\) Exercise \(217\)

    In Problem 216 you see that when we added numerical multiples of the reciprocals of first degree polynomials we got a fraction in which the denominator is a quadratic polynomial. This will always happen unless the two denominators are multiples of each other, because their least common multiple will simply be their product, a quadratic polynomial. This leads us to ask whether a fraction whose denominator is a quadratic polynomial can always be expressed as a sum of fractions whose denominators are first degree polynomials. Find numbers \(c\) and \(d\) so that

    \[\dfrac{5x + 1}{(x − 3)(x + 5)} = \dfrac{c}{x − 3} + \dfrac{d}{x + 5} .\] (Hint).

    \(\bullet\) Exercise \(218\)

    In Problem 217 you may have simply guessed at values of \(c\) and \(d\), or you may have solved a system of equations in the two unknowns \(c\) and \(d\). Given constants \(a\), \(b\), \(r_1\), and \(r_2\) (with \(r_1 \neq r_2\)), write down a system of equations we can solve for \(c\) and \(d\) to write

    \[\dfrac{ax + b}{(x − r_1)(x − r_2)} = \dfrac{c}{x − r_1} + \dfrac{d}{x − r_2}.\] (Hint).

    Writing down the equations in Problem 218 and solving them is called the method of partial fractions. This method will let you find power series expansions for generating functions of the type you found in Problems 213 to Problem 215. However, you have to be able to factor the quadratic polynomials that are in the denominators of your generating functions.

    \(\bullet\) Exercise \(219\)

    Use the method of partial fractions to convert the generating function of Problem 213 into the form \[\dfrac{c}{x − r_1} + \dfrac{d}{x − r_2}.\] Use this to find a formula for \(a_n\).

    \(\bullet\) Exercise \(220\)

    Use the quadratic formula to find the solutions to \(x^2 +x−1 = 0\), and use that information to factor \(x^2 + x − 1\).

    \(\bullet\) Exercise \(221\)

    Use the factors you found in Problem 220 to write \[\dfrac{1}{x^2 + x − 1}\] in the form \[\dfrac{c}{x − r_1} + \dfrac{d}{x − r_2}.\] (Hint).

    \(\bullet\) Exercise \(222\)

    a. Use the partial fractions decomposition you found in Problem 220 to write the generating function you found in Problem 214 in the form \[\sum^{∞}_{n=0} a_n x^i\] and use this to give an explicit formula for \(a_n\). (Hint).

    b. When we have \(a_0 = 1\) and \(a_1 = 1\), i.e. when we start with one pair of baby rabbits, the numbers \(a_n\) are called Fibonacci Numbers. Use either the recurrence or your final formula to find \(a_2\) through \(a_8\). Are you amazed that your general formula produces integers, or for that matter produces rational numbers? Why does the recurrence equation tell you that the Fibonacci numbers are all integers?

    c. Explain why there is a real number \(b\) such that, for large values of \(n\), the value of the \(n^{\text{th}}\) Fibonacci number is almost exactly (but not quite) some constant times \(b^n\). (Find \(b\) and the constant.)

    d. Find an algebraic explanation (not using the recurrence equation) of what happens to make the square roots of five go away. (Hint).

    e. As a challenge (which the author has not yet done), see if you can find a way to show algebraically (not using the recurrence relation, but rather the formula you get by removing the square roots of five) that the formula for the Fibonacci numbers yields integers.

    Exercise \(223\)

    Solve the recurrence \(a_n = 4a_{n−1} − 4a_{n−2}\).

    4.3.5: Catalan Numbers

    \(\rightarrow\) Exercise \(224\)

    a. Using either lattice paths or diagonal lattice paths, explain why the Catalan Number \(c_n\) satisfies the recurrence \[C_n = \sum^{n−1}_{i=1} C_{i−1}C_{n−i}.\] (Hint).

    b. Show that if we use \(y\) to stand for the power series \(\sum^{∞}_{n=0} c_n x^n\), then we can find \(y\) by solving a quadratic equation. Find \(y\). (Hint).

    c. Taylor’s theorem from calculus tells us that the extended binomial theorem \[ (1 + x)^r = \sum^{∞}_{i=0} \binom{r}{i}x^i \] holds for any number real number \(r\), where \( \binom{r}{i} \) is defined to be \[\dfrac{r^{\underline{i}}}{i!} = \dfrac{r(r − 1)···(r − i + 1)}{i!}.\] Use this and your solution for \(y\) (note that of the two possible values for \(y\) that you get from the quadratic formula, only one gives an actual power series) to get a formula for the Catalan numbers. (Hint).


    This page titled 4.3: Generating Functions and Recurrence Relations is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Kenneth P. Bogart.