CTGD Generating Functions and Recurrence Relations

Section 4.3 Generating Functions and Recurrence Relations

Recall that a recurrence relation for a sequence $a_n$ expresses $a_n$ in terms of values $a_i$ for $i\lt n\text{.}$ For example, the equation $a_i=3a_{i-1} +2^i$ is a first order linear constant coefficient recurrence.

Subsection 4.3.1 How generating functions are relevant

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

Problem 211

Suppose that $a_i=3a_{i-1} + 3^i\text{.}$

(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

\begin{equation*} \sum_{i=1}^\infty a_ix^i = (\sum_{i=0}^\infty a_ix^i) -a_0 \end{equation*}

and in the right hand side, use the fact that

\begin{equation*} \sum_{i=1}^\infty a_{i-1}x^i = x\sum_{i=1}^\infty a_{i-1}x^{i-1} =x\sum_{j=0}^\infty a_jx^j =x\sum_{i=0}^\infty a_ix^i \end{equation*}

(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}^\infty a_ix^i\text{.}$ Solve the resulting equation for the power series $\sum_{i=0}^\infty a_ix^i\text{.}$ 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\text{.}$

(c)

Now suppose that $a_i=3a_{i-1} + 2^i\text{.}$ 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

You may run into a product of the form $\sum_{i=0}^\infty a^ix^i\sum_{j=0}^\infty b^jx^j\text{.}$ Note that in the product, the coefficient of $x^k$ is $\sum_{i=0}^k a^ib^{k-i} = \sum_{i=0}^k \frac{a^i}{b^i}\text{.}$

Problem 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\text{,}$ write a recurrence for the amount of money the certificate is worth at the end of year $n\text{.}$ 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?

Subsection 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 Fibonacci⁶Apparently Leonardo da Pisa was given the name Fibonacci posthumously. It is a shortening of “son of Bonacci” in Italian. introduced them, he did so with a fictional population of rabbits.

Subsection 4.3.3 Second order linear recurrence relations

Problem 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\text{.}$ Show that $a_n=a_{n-1} + 2a_{n-2}\text{.}$ This is an example of a second order linear recurrence with constant coefficients. Using a method similar to that of Problem 211, show that

\begin{equation*} \sum_{i=0}^\infty a_ix^i = \frac{10}{1-x-2x^2}. \end{equation*}

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

Problem 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

Our recurrence becomes $a_n = a_{n-1} + a_{n-2}\text{.}$

Problem 215

Find the generating function for the solutions to the recurrence

\begin{equation*} a_i=5a_{i-1}-6a_{i-2} + 2^i. \end{equation*}

The recurrence relations we have seen in this section are called second order because they specify $a_i$ in terms of $a_{i-1}$ and $a_{i-2}\text{,}$ 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.

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

Problem 216

Express $\frac{1}{x-3} + \frac{2}{x-2}$ as a single fraction.

Problem 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

\begin{equation*} \frac{5x+1}{(x-3)(x+5)} = \frac{c}{x-3} + \frac{d}{x+5}. \end{equation*}

Hint

\begin{equation*} \frac{5x+1}{(x-3)(x-5)} = \frac{cx+5c+dx-3d}{(x-3)(x-5)} \end{equation*}

gives us

\begin{align*} 5x \amp = cx+dx\\ 1 \amp= 5c-3d\text{.} \end{align*}

Problem 218

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

\begin{equation*} \frac{ax+b}{(x-r_1)(x-r_2)} = \frac{c}{x-r_1} + \frac{d}{x-r_2}\text{.} \end{equation*}

Hint

To have

\begin{equation*} \frac{ax+b}{(x-r_1)(x-r_2)} = \frac{c}{x-r_1} + \frac{d}{x-r_2} \end{equation*}

we must have

\begin{equation*} cx-r_2c+dx-r_1d =ax+b\text{.} \end{equation*}

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.

Problem 219

Use the method of partial fractions to convert the generating function of Problem 213 into the form

\begin{equation*} \frac{c}{x-r_1} + \frac{d}{x-r_2}\text{.} \end{equation*}

Use this to find a formula for $a_n\text{.}$

Problem 220

Use the quadratic formula to find the solutions to $x^2+x-1=0\text{,}$ and use that information to factor $x^2+x-1\text{.}$

Problem 221

Use the factors you found in Problem 220 to write

\begin{equation*} \frac{1}{x^2+x-1} \end{equation*}

in the form

\begin{equation*} \frac{c}{x-r_1} + \frac{d}{x-r_2}. \end{equation*}

Hint

You can save yourself a tremendous amount of frustrating algebra if you arbitrarily choose one of the solutions and call it $r_1$ and call the other solution $r_2$ and solve the problem using these algebraic symbols in place of the actual roots.⁷We use the words roots and solutions interchangeably. Not only will you save yourself some work, but you will get a formula you could use in other problems. When you are done, substitute in the actual values of the solutions and simplify.

Problem 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

\begin{equation*} \sum_{n=0}^\infty a_nx^i \end{equation*}

and use this to give an explicit formula for $a_n\text{.}$

Hint

Once again it will save a lot of tedious algebra if you use the symbols $r_1$ and $r_2$ for the solutions as in Problem 221 and substitute the actual values of the solutions once you have a formula for $a_n$ in terms of $r_1$ and $r_2\text{.}$

(b)

When we have $a_0=1$ and $a_1=1\text{,}$ 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\text{.}$ 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\text{,}$ the value of the $n$th Fibonacci number is almost exactly (but not quite) some constant times $b^n\text{.}$ (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

Think about how the binomial theorem might help you.

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

Problem 223

Solve the recurrence $a_n= 4a_{n-1} - 4a_{n-2}\text{.}$

Subsection 4.3.5 Catalan Numbers

Problem 224

(a)

Using either lattice paths or diagonal lattice paths, explain why the Catalan Number $c_n$ satisfies the recurrence

\begin{equation*} C_n = \sum_{i=1}^{n-1} C_{i-1}C_{n-i}\text{.} \end{equation*}

Hint

A Catalan path could touch the $x$-axis several times before it reaches $(2n, 0)\text{.}$ Its first touch can be any point $(2i, 0)$ between $(2, 0)$ and $(2n, 0)\text{.}$ For the path to touch first at $(2i, 0)\text{,}$ the path must start with an upstep and then proceed as a Dyck path from $(1, 1)$ to $(2i - 1, 1)\text{.}$ From there it must take a downstep. Can you see a bijection between such Dyck paths and Catalan paths of a certain kind?

(b)

Show that if we use $y$ to stand for the power series $\sum_{n=0}^\infty c_nx^n\text{,}$ then we can find $y$ by solving a quadratic equation. Find $y\text{.}$

Hint

Does the right-hand side of the recurrence remind you of some products you have worked with?

(c)

Taylor's theorem from calculus tells us that the extended binomial theorem

\begin{equation*} (1+x)^r = \sum_{i=0}^\infty \binom{r}{i}x^i \end{equation*}

holds for any number real number $r\text{,}$ where $\binom{r}{i}$ is defined to be

\begin{equation*} \frac{r^{\underline{i}}}{i!} = \frac{r(r-1)\cdots(r-i+1)}{i!} \text{.} \end{equation*}

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

\begin{equation*} \frac{1\cdot 3\cdot 5\cdots (2i-3)}{i!} = \frac{(2i-2)!}{(i-1)!2^i i!}\text{.} \end{equation*}