Section3.3Generating Functions
¶In this section we will consider how to use polynomials to help us solve counting problems. Why would we even think there would be a connection here?
Activity233
Suppose you have two number cubes with non-standard labels. The first has 1's on four sides and 2's on the remaining two sides, while the second cube has two 1's and four 2's. You will roll the pair of dice and compute the sum of the numbers rolled.
(a)
How many ways could you roll a 2? What about a 3? 4? You should be able to answer these questions by making a \(6\times 6\) addition table (with a lot of repeated row and column headers), but make sure you also think about how the sum and product principles are being used.
(b)
Expand the polynomial \((4x + 2x^2)(2x + 4x^2)\text{.}\) Do this by hand, keeping track of what you get before and after you “group like terms.”
(c)
How are the two tasks above related? What is going on here?
Activity234
(a)
Complete the standard addition table used to count the number of ways each sum of two dice can be achieved. What would you do with the entries in the table to find the number of ways to roll an 8, for example?
(b)
How is the table above related to what you would get if you complete the table below?
|
\(x\) |
\(x^2\) |
\(x^3\) |
\(x^4\) |
\(x^5\) |
\(x^6\) |
| \(x\) |
|
|
|
|
|
|
| \(x^2\) |
|
|
|
|
|
|
| \(x^3\) |
|
|
|
|
|
|
| \(x^4\) |
|
|
|
|
|
|
| \(x^5\) |
|
|
|
|
|
|
| \(x^6\) |
|
|
|
|
|
|
In particular, what should the operation on the table be to make the correspondence relevant?
HintIf you were to treat this as an addition table, then you would have entries like \(x^2+x^3\text{.}\) But the corresponding table for the dice has a 5 in that position.
(c)
What do each of the tasks above have to do with expanding \((x+x^2 + \cdots +x^6)^2\)
Activity235
It is also possible to multiply infinite polynomials (i.e., power series). As long as we are only interested in the first few terms, we can find these by multiplying a small number of terms from the two infinite polynomials.
(a)
Multiply \((1+x+x^2+x^3 + \cdots)(1+ x + x^2 + x^3+ \cdots)\text{.}\)
(b)
Multiply \((1+x+x^2 + x^3 + \cdots)(x + 2x + 3x^3 + 4x^4 + \cdots)\text{.}\)
(c)
What is going on here? Where have we seen the coefficients of these polynomials before?
Subsection3.3.1Visualizing Counting with Pictures
¶Suppose you are going to choose three pieces of fruit from among apples, pears and bananas for a snack. We can symbolically represent all your choices as
\begin{equation*}
\ap\ap\ap+\pe\pe\pe+\ba\ba\ba+\ap\ap\pe+\ap\ap\ba+\ap\pe\pe +\pe\pe\ba
+\ap\ba\ba+\pe\ba\ba+\ap\pe\ba.
\end{equation*}
Here we are using a picture of a piece of fruit to stand for taking a piece of that fruit. Thus \(\ap\) stands for taking an apple, \(\ap\pe\) for taking an apple and a pear, and \(\ap\ap\) for taking two apples. You can think of the plus sign as standing for the “exclusive or,” that is, \(\ap+\ba\) would stand for “I take an apple or a banana but not both.” To say “I take both an apple and a banana,” we would write \(\ap\ba\text{.}\) We can extend the analogy to mathematical notation by condensing our statement that we take three pieces of fruit to
\begin{equation*}
\ap^3+\pe^3+\ba^3+\ap^2\pe+\ap^2\ba +\ap\pe^2+\pe^2\ba+
\ap\ba^2+\pe\ba^2 +\ap\pe\ba.
\end{equation*}
In this notation \(\ap^3\) stands for taking a multiset of three apples, while \(\ap^2\ba\) stands for taking a multiset of two apples and a banana, and so on. What our notation is really doing is giving us a convenient way to list all three element multisets chosen from the set \(\{\ap,\pe,\ba\}\text{.}\)
Suppose now that we plan to choose between one and three apples, between one and two pears, and between one and two bananas. In a somewhat clumsy way we could describe our fruit selections as
\begin{align}
\ap\pe\ba\amp+\ap^2\pe\ba\amp+\cdots\amp+\ap^2\pe^2\ba
\amp+\cdots \amp+
\ap^2\pe^2\ba^2 \notag\\
\amp+\ap^3\pe\ba\amp+
\cdots \amp+\ap^3\pe^2\ba\amp+\cdots \amp+
\ap^3\pe^2\ba^2.\label{uptothreefruits}\tag{3.3}
\end{align}
Activity236
Using an \(A\) in place of the picture of an apple, a \(P\) in place of the picture of a pear, and a \(B\) in place of the picture of a banana, write out the formula similar to Formula (3.3) without any dots for left out terms. (You may use pictures instead of letters if you prefer, but it gets tedious quite quickly!) Now expand the product \((A+A^2+A^3)(P+P^2)(B+B^2)\) and compare the result with your formula.
Activity237
Substitute \(x\) for all of \(A\text{,}\) \(P\) and \(B\) (or for the corresponding pictures) in the formula you got in Activity 236 and expand the result in powers of \(x\text{.}\) Give an interpretation of the coefficient of \(x^n\text{.}\)
If we were to expand the formula
\begin{equation}
(\ap+\ap^2+\ap^3)(\pe+\pe^2)(\ba+\ba^2).\label{threefruitsagain}\tag{3.4}
\end{equation}
we would get Formula (3.3). Thus Formula (3.3) and Formula (3.4) each describe the number of multisets we can choose from the set \(\{\ap,\pe,\ba\}\) in which \(\apple\) appears between 1 and three times and \(\pear\) and \(\banana\) each appear once or twice. We interpret Formula (3.3) as describing each individual multiset we can choose, and we interpret Formula (3.4) as saying that we first decide how many apples to take, and then decide how many pears to take, and then decide how many bananas to take. At this stage it might seem a bit magical that doing ordinary algebra with the second formula yields the first, but in fact we could define addition and multiplication with these pictures more formally so we could explain in detail why things work out. However since the pictures are for motivation, and are actually difficult to write out on paper, it doesn't make much sense to work out these details. We will see an explanation in another context later on.
Subsection3.3.2Picture functions
¶As you've seen, in our descriptions of ways of choosing fruits, we've treated the pictures of the fruit as if they are variables. You've also likely noticed that it is much easier to do algebraic manipulations with letters rather than pictures, simply because it is time consuming to draw the same picture over and over again, while we are used to writing letters quickly. In the theory of generating functions, we associate variables or polynomials or even power series with members of a set. There is no standard language describing how we associate variables with members of a set, so we shall invent some. By a picture of a member of a set we will mean a variable, or perhaps a product of powers of variables (or even a sum of products of powers of variables). A function that assigns a picture \(P(s)\) to each member \(s\) of a set \(S\) will be called a picture function . The picture enumerator for a picture function \(P\) defined on a set \(S\) will be
\begin{equation*}
E_P(S) = \sum_{s: s\in S} P(s).
\end{equation*}
We choose this language because the picture enumerator lists, or enumerates, all the elements of \(S\) according to their pictures. Thus Formula (3.3) is the picture enumerator the set of all multisets of fruit with between one and three apples, one and two pears, and one and two bananas.
Activity238
How would you write down a polynomial in the variable \(A\) that says you should take between zero and three apples?
Activity239
How would you write down a picture enumerator that says we take between zero and three apples, between zero and three pears, and between zero and three bananas?
Activity240
Notice that when we used \(A^2\) to stand for taking two apples, and \(P^3\) to stand for taking three pears, then we used the product \(A^2P^3\) to stand for taking two apples and three pears. Thus we have chosen the picture of the ordered pair (2 apples, 3 pears) to be the product of the pictures of a multiset of two apples and a multiset of three pears. Show that if \(S_1\) and \(S_2\) are sets with picture functions \(P_1\) and \(P_2\) defined on them, and if we define the picture of an ordered pair \((x_1,x_2)\in S_1\times S_2\) to be \(P((x_1,x_2))= P_1(x_1)P_2(x_2)\text{,}\) then the picture enumerator of \(P\) on the set \(S_1\times S_2\) is \(E_{P_1}(S_1)E_{P_2}(S_2)\text{.}\) We call this the product principle for picture enumerators.
Subsection3.3.3Generating functions
¶
Activity241
Suppose you are going to choose a snack of between zero and three apples, between zero and three pears, and between zero and three bananas. Write down a polynomial in one variable \(x\) such that the coefficient of \(x^n\) is the number of ways to choose a snack with \(n\) pieces of fruit.
HintSubstitute something for \(A\text{,}\) \(P\) and \(B\) in your formula from Activity 239.
Activity242
Suppose an apple costs 20 cents, a banana costs 25 cents, and a pear costs 30 cents. What should you substitute for \(A\text{,}\) \(P\text{,}\) and \(B\) in Activity 239 in order to get a polynomial in which the coefficient of \(x^n\) is the number of ways to choose a selection of fruit that costs \(n\) cents?
HintFor example, to get the cost of the fruit selection \(AP B\) you would want to get \(x^{20} x^{25} x^{30} = x^{75}\text{.}\)
Activity243
Suppose an apple has 40 calories, a pear has 60 calories, and a banana has 80 calories. What should you substitute for \(A\text{,}\) \(P\text{,}\) and \(B\) in Activity 239 in order to get a polynomial in which the coefficient of \(x^n\) is the number of ways to choose a selection of fruit with a total of \(n\) calories?
Activity244
We are going to choose a subset of the set \([n]=\{1,2,\ldots, n\}\text{.}\) Suppose we use \(x_1\) to be the picture of choosing 1 to be in our subset. What is the picture enumerator for either choosing 1 or not choosing 1? Suppose that for each \(i\) between 1 and \(n\text{,}\) we use \(x_i\) to be the picture of choosing \(i\) to be in our subset. What is the picture enumerator for either choosing \(i\) or not choosing \(i\) to be in our subset? What is the picture enumerator for all possible choices of subsets of \([n]\text{?}\) What should we substitute for \(x_i\) in order to get a polynomial in \(x\) such that the coefficient of \(x^k\) is the number of ways to choose a \(k\)-element subset of \(n\text{?}\) What theorem have we just reproved (a special case of)?
HintConsider the example with \(n = 2\text{.}\) Then we have two variables, \(x_1\) and \(x_2\) . Forgetting about \(x_2\) , what sum says we either take \(x_1\) or we don't? Forgetting about \(x_1\) , what sum says we either take \(x_2\) or we don't? Now what product says we either take \(x_1\) or we don't and we either take \(x_2\) or we don't?
In Activity 244 we see that we can think of the process of expanding the polynomial \((1+x)^n\) as a way of “generating” the binomial coefficients \(\binom{n}{k}\) as the coefficients of \(x^k\) in the expansion of \((1+x)^n\text{.}\) For this reason, we say that \((1+x)^n\) is the “generating function” for the binomial coefficients \(\binom{n}{k}\text{.}\) More generally, the generating function for a sequence \(a_i\text{,}\) defined for \(i\) with \(0\le i\le n\) is the expression \(\sum_{i=0}^n a_ix^i\text{,}\) and the generating function for the sequence \(a_i\) with \(i\ge 0\) is the expression \(\sum_{i=0}^\infty a_ix^i\text{.}\) This last expression is an example of a power series. In calculus it is important to think about whether a power series converges in order to determine whether or not it represents a function. In a nice twist of language, even though we use the phrase generating function as the name of a power series in combinatorics, we don't require the power series to actually represent a function in the usual sense, and so we don't have to worry about convergence. Instead we think of a power series as a convenient way of representing the terms of a sequence of numbers of interest to us. The only justification for saying that such a representation is convenient is because of the way algebraic properties of power series capture some of the important properties of some sequences that are of combinatorial importance. The remainder of this chapter is devoted to giving examples of how the algebra of power series reflects combinatorial ideas.
Because we choose to think of power series as strings of symbols that we manipulate by using the ordinary rules of algebra and we choose to ignore issues of convergence, we have to avoid manipulating power series in a way that would require us to add infinitely many real numbers. For example, we cannot make the substitution of \(y+1\) for \(x\) in the power series \(\sum_{i=0}^\infty x^i\text{,}\) because in order to interpret \(\sum_{i=0}^\infty (y+1)^i\) as a power series we would have to apply the binomial theorem to each of the \((y+1)^i\) terms, and then collect like terms, giving us infinitely many ones added together as the coefficient of \(y^0\text{,}\) and in fact infinitely many numbers added together for the coefficient of any \(y^i\text{.}\) (On the other hand, it would be fine to substitute \(y+y^2\) for \(x\text{.}\) Can you see why?)
Subsection3.3.4Power series
¶For now, most of our uses of power series will involve just simple algebra. Since we use power series in a different way in combinatorics than we do in calculus, we should review a bit of the algebra of power series.
Activity245
In the polynomial \((a_0 +a_1x+a_2x^2)(b_0+b_1x+b_2x^2+b_3x^3)\text{,}\) what is the coefficient of \(x^2\text{?}\) What is the coefficient of \(x^4\text{?}\)
Activity246
In Activity 245 why is there a \(b_0\) and a \(b_1\) in your expression for the coefficient of \(x^2\) but there is not a \(b_0\) or a \(b_1\) in your expression for the coefficient of \(x^4\text{?}\) What is the coefficient of \(x^4\) in
\begin{equation*}
(a_0+a_1x+a_2x^2+a_3x^3+a_4x^4)(b_0+b_1x+b_2x^2
+b_3x^3+b_4x^4)?
\end{equation*}
Express this coefficient in the form
\begin{equation*}
\sum_{i=0}^4 \mbox{ something} ,
\end{equation*}
where the something is an expression you need to figure out. Now suppose that \(a_3=0\text{,}\) \(a_4=0\) and \(b_4=0\text{.}\) To what is your expression equal after you substitute these values? In particular, what does this have to do with Activity 245?
HintFor the last two questions, try multiplying out something simpler first, say \((a_0 + a_1 x + a_2 x^2 )(b_0 + b_1 x + b_2 x^2 )\) . If this problem seems difficult the part that seems to cause students the most problems is converting the expression they get for a product like this into summation notation. If you are having this kind of problem, expand the product \((a_0 + a_1 x + a_2 x^2 )(b_0 + b_1 x + b_2 x^2 )\) and then figure out what the coefficient of \(x^2\) is. Try to write that in summation notation.
Activity247
The point of the Problems 245 and Activity 246 is that so long as we are willing to assume \(a_i=0\) for \(i>n\) and \(b_j =0\) for \(j>m\text{,}\) then there is a very nice formula for the coefficient of \(x^k\) in the product
\begin{equation*}
\left(\sum_{i=0}^n a_ix^i\right)\left(\sum_{j=0}^m b_jx^j\right).
\end{equation*}
Write down this formula explicitly.
HintWrite down the formulas for the coefficients of \(x^0\text{,}\) \(x^1\text{,}\) \(x^2\) and \(x^3\) in
\begin{equation*}
\left(\sum_{i=0}^n a_ix^i\right)\left(\sum_{j=0}^m b_jx^j\right)\text{.}
\end{equation*}
Activity248
Assuming that the rules you use to do arithmetic with polynomials apply to power series, write down a formula for the coefficient of \(x^k\) in the product
\begin{equation*}
\left(\sum_{i=0}^\infty a_ix^i\right)\left(\sum_{j=0}^\infty
b_jx^j\right)\text{.}
\end{equation*}
HintHow is this problem different from Activity 247? Is this an important difference from the point of view of the coefficient of \(x^k\text{?}\)
We use the expression you obtained in Activity 248 to define the product of power series. That is, we define the product
\begin{equation*}
\left(\sum_{i=0}^\infty a_ix^i\right)\left(\sum_{j=0}^\infty
b_jx^j\right)
\end{equation*}
to be the power series \(\sum_{k=0}^\infty c_k x^k\text{,}\) where \(c_k\) is the expression you found in Activity 248. Since you derived this expression by using the usual rules of algebra for polynomials, it should not be surprising that the product of power series satisfies these rules.
Subsection3.3.5Product principle for generating functions
¶Each time that we converted a picture function to a generating function by substituting \(x\) or some power of \(x\) for each picture, the coefficient of \(x\) had a meaning that was significant to us. For example, with the picture enumerator for selecting between zero and three each of apples, pears, and bananas, when we substituted \(x\) for each of our pictures, the exponent \(i\) in the power \(x^i\) is the number of pieces of fruit in the fruit selection that led us to \(x^i\text{.}\) After we simplify our product by collecting together all like powers of \(x\text{,}\) the coefficient of \(x^i\) is the number of fruit selections that use \(i\) pieces of fruit. In the same way, if we substitute \(x^c\) for a picture, where \(c\) is the number of calories in that particular kind of fruit, then the \(i\) in an \(x^i\) term in our generating function stands for the number of calories in a fruit selection that gave rise to \(x^i\text{,}\) and the coefficient of \(x^i\) in our generating function is the number of fruit selections with \(i\) calories. The product principle of picture enumerators translates directly into a product principle for generating functions.
Activity249
Suppose that we have two sets \(S_1\) and \(S_2\text{.}\) Let \(v_1\) (\(v\) stands for value) be a function from \(S_1\) to the nonnegative integers and let \(v_2\) be a function from \(S_2\) to the nonnegative integers. Define a new function \(v\) on the set \(S_1 \times S_2\) by \(v(x_1,x_2) = v_1(x_1) +v_2(x_2)\text{.}\) Suppose further that \(\sum_{i=0}^\infty a_ix^i\) is the generating function for the number of elements \(x_1\) of \(S_1\) of value \(i\text{,}\) that is with \(v_1(x_1)=i\text{.}\) Suppose also that \(\sum_{j=0}^\infty b_j x^j\) is the generating function for the number of elements of \(x_2\) of \(S_2\) of value \(j\text{,}\) that is with \(v_2(x_2) = j\text{.}\) Prove that the coefficient of \(x^k\) in
\begin{equation*}
\left(\sum_{i=0}^\infty a_ix^i\right)\left(\sum_{j=0}^\infty
b_jx^j\right)
\end{equation*}
is the number of ordered pairs \((x_1,x_2)\) in \(S_1\times S_2\) with total value \(k\text{,}\) that is with \(v_1(x_1) +v_2(x_2) =k\text{.}\) This is called the product principle for generating functions.
HintIf this problem appears difficult, the most likely reason is because the definitions are all new and symbolic. Focus on what it means for \(\sum_{k=0}^\infty c_kx^k\) to be the generating function for ordered pairs of total value \(k\text{.}\) In particular, how do we get an ordered pair with total value \(k\text{?}\) What do we need to know about the values of the components of the ordered pair?
Activity 249 may be extended by mathematical induction to prove our next theorem.
Theorem3.3.1
If \(S_1,S_2,\dots,S_n\) are sets with a value function \(v_i\) from \(S_i\) to the nonnegative integers for each \(i\) and \(f_i(x)\) is the generating function for the number of elements of \(S_i\) of each possible value, then the generating function for the number of \(n\)-tuples of each possible value is \(\prod_{i=1}^n f_i(x)\text{.}\)
Subsection3.3.6The extended binomial theorem and multisets
¶
Activity250
Suppose once again that \(i\) is an integer between 1 and \(n\text{.}\)
(a)
What is the generating function in which the coefficient of \(x^k\) is \(1\text{?}\) This series is an example of what is called an infinite geometric series. In the next part of this problem, it will be useful to interpret the coefficient one as the number of multisets of size \(k\) chosen from the singleton set \(\{i\}\text{.}\) Namely, there is only one way to choose a multiset of size \(k\) from \(\{i\}\text{:}\) choose \(i\) exactly \(k\) times.
(b)
Express the generating function in which the coefficient of \(x^k\) is the number of multisets chosen from \([n]\) as a power of a power series. What does Theorem 2.3.3 (in which your answer could be expressed as a binomial coefficient) tell you about what this generating function equals?
Hint1You might try applying the product principle for generating functions to an appropriate power of the generating function you got in the first part of this problem.
In Theorem 2.3.3 we have a formula for the number of \(k\)-element multisets chosen from an \(n\)-element set. Suppose you use this formula for \(a_k\) in \(\sum_{k=0}^\infty a_kx^k\text{.}\) What do you get the generating function for?
Activity251
What is the product \((1-x)\sum_{k=0}^n x^k\text{?}\) What is the product
\begin{equation*}
(1-x)\sum_{k=0}^\infty x^k?
\end{equation*}
Activity252
Express the generating function for the number of multisets of size \(k\) chosen from \([n]\) (where \(n\) is fixed but \(k\) can be any nonnegative integer) as a 1 over something relatively simple.
Activity253
Find a formula for \((1+x)^{-n}\) as a power series whose coefficients involve binomial coefficients. What does this formula tell you about how we should define \(\binom{-n}{k}\) when \(n\) is positive?
Hint1While you could use calculus techniques, there is a much simpler approach. Note that \(1 + x = 1 - (-x)\text{.}\)
Can you see a way to use Activity 252?
Activity254
If you define \(\binom{-n}{k}\) in the way you described in Activity 253, you can write down a version of the binomial theorem for \((x+y)^n\) that is valid for both nonnegative and negative values of \(n\text{.}\) Do so. This is called the extended binomial theorem. Write down a special case with \(n\) negative, like \(n=-3\text{,}\) to see an interesting surprise that suggests why we do not use this formula later on.
Activity255
Write down the generating function for the number of ways to distribute identical pieces of candy to three children so that no child gets more than 4 pieces. Write this generating function as a quotient of polynomials. Using both the extended binomial theorem and the original binomial theorem, find out in how many ways we can pass out exactly ten pieces.
Hint1Look for a power of a polynomial to get started.
The polynomial referred to in the first hint is a quotient of two polynomials. The power of the denominator can be written as a power series.
Activity256
Another way to count the number of ways to distribute 10 identical pieces of candy to 3 children so no child gets more than 4 is to use the Principle of Inclusion and Exclusion. Do this, and compare this calculation to what you found in Activity 255.
Activity257
What is the generating function for the number of multisets chosen from an \(n\)-element set so that each element appears at least \(j\) times and less than \(m\) times? Write this generating function as a quotient of polynomials, then as a product of a polynomial and a power series.
Subsection3.3.7Generating 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.
Algebraic manipulations with generating functions can sometimes reveal the solutions to a recurrence relation.
Activity258
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 x^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_ix^{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.)
HintYou 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{.}\)
Activity259
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?
Subsection3.3.8Fibonacci numbers
¶The sequence of problems that follows (culminating in Activity 269) 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 introduced them, he did so with a fictional population of rabbits.
Activity260
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 Activity 258, 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.
Activity261
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 Activity 260. 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.
HintOur recurrence becomes \(a_n = a_{n-1} + a_{n-2}\text{.}\)
Activity262
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.
Subsection3.3.9Partial 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.
Activity263
Express \(\frac{1}{x-3} + \frac{2}{x-2}\) as a single fraction.
Activity264
In Activity 263 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*}
Activity265
In Activity 264 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*}
HintTo 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 Activity 265 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 260 to Activity 262. However you have to be able to factor the quadratic polynomials that are in the denominators of your generating functions.
Activity266
Use the method of partial fractions to convert the generating function of Activity 260 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{.}\)
Activity267
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{.}\)
Activity268
Use the factors you found in Activity 267 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*}
HintYou 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. 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.
Activity269
(a)
Use the partial fractions decomposition you found in Activity 267 to write the generating function you found in Activity 261 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{.}\)
HintOnce again it will save a lot of tedious algebra if you use the symbols \(r_1\) and \(r_2\) for the solutions as in Activity 268 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.
HintThink 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.
Activity270
Solve the recurrence \(a_n= 4a_{n-1} - 4a_{n-2}\text{.}\)
Subsection3.3.10Catalan Numbers
¶
Activity271
Recall the recurrence for the Catalan numbers is
\begin{equation*}
C_n = \sum_{i=1}^{n-1} C_{i-1}C_{n-i}\text{.}
\end{equation*}
(a)
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{.}\)
HintDoes the right-hand side of the recurrence remind you of some products you have worked with?
(b)
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*}