Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

4.3: Generating Functions and Recurrence Relations

( \newcommand{\kernel}{\mathrm{null}\,}\)

Recall that a recurrence relation for a sequence an expresses an in terms of values ai for i<n. For example, the equation ai=3ai1+2i 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.

Exercise 211

Suppose that ai=3ai1+3i.

a. Multiply both sides by xi 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

i=1aixi=(i=0xi)a0

and in the right hand side, use the fact that

i=1ai1xi=xi=1aixi1=xj=0ajxj=xi=0aixi

(where we substituted j for i1 to see explicitly how to change the limits of summation, a surprisingly useful trick) to rewrite the equation in terms of the power series i=0aixi. Solve the resulting equation for the power series i=0aixi. 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 ai in terms of a0.

c. Now suppose that ai=3ai1+2i. 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).

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 ai 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

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 an be the number of rabbits we have at the end of month n. Show that an=an1+2an2. This is an example of a second order linear recurrence with constant coefficients. Using a method similar to that of Problem 211, show that

i=0aixi=101x2x2

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

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).

Exercise 215

Find the generating function for the solutions to the recurrence ai=5ai16ai2+2i.

The recurrence relations we have seen in this section are called second order because they specify ai in terms of ai1 and ai2, they are called linear because ai1 and ai2 each appear to the first power, and they are called constant coefficient recurrences because the coefficients in front of ai1 and ai2 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.

Exercise 216

Express 1x3+2x2 as a single fraction.

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

5x+1(x3)(x+5)=cx3+dx+5. (Hint).

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, r1, and r2 (with r1r2), write down a system of equations we can solve for c and d to write

ax+b(xr1)(xr2)=cxr1+dxr2. (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.

Exercise 219

Use the method of partial fractions to convert the generating function of Problem 213 into the form cxr1+dxr2. Use this to find a formula for an.

Exercise 220

Use the quadratic formula to find the solutions to x2+x1=0, and use that information to factor x2+x1.

Exercise 221

Use the factors you found in Problem 220 to write 1x2+x1 in the form cxr1+dxr2. (Hint).

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 n=0anxi and use this to give an explicit formula for an. (Hint).

b. When we have a0=1 and a1=1, i.e. when we start with one pair of baby rabbits, the numbers an are called Fibonacci Numbers. Use either the recurrence or your final formula to find a2 through a8. 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 nth Fibonacci number is almost exactly (but not quite) some constant times bn. (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 an=4an14an2.

4.3.5: Catalan Numbers

Exercise 224

a. Using either lattice paths or diagonal lattice paths, explain why the Catalan Number cn satisfies the recurrence Cn=n1i=1Ci1Cni. (Hint).

b. Show that if we use y to stand for the power series n=0cnxn, 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=i=0(ri)xi holds for any number real number r, where (ri) is defined to be ri_i!=r(r1)···(ri+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.

Support Center

How can we help?