Generating Functions

Section 2.2 Generating 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?

Activity 150.

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?

Activity 151.

A standard problem to use when introducing probability is to ask for the probability of rolling a particular sum on two regular number cubes (dice numbered 1 through 6). Students might not immediately see that some sums are more likely to occur than others. You can illustrate this by creating a table.

(a)

Complete the standard addition table used to count the number of ways each sum of two regular 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?

Hint

If 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$

Exercise 152.

Using the connection between dice and polynomials, we can find interesting ways to label dice without modifying probabilities.

(a)

Show algebraically that $x+x^2 + x^3 + x^4 + x^5 + x^6 = x(1+x+x^2)(1+x)(1-x+x^2)\text{.}$ Try to do this by factoring instead of multiplying out the right-hand side.

(b)

Multiply out the polynomial $x(x+1)(x^2+x+1)$ and also $x(x+1)(x^2+x+1)(x^2-x+1)^2\text{.}$

(c)

Explain how the previous two parts together allow you to find another way to label dice so that the probability of throwing any number 2 to 12 is the same as for standard dice.

Hint

The new labeling will be $\{1,2, 2, 3, 3, 4\}$ and $\{1, 3, 4, 5, 6, 8\}\text{.}$ These are called Sicherman dice. Now explain how the polynomials prove that the probabilities for these dice will match standard dice.

Activity 153.

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. Multiply the following series out through at least $x^7\text{.}$

(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^2 + 3x^3 + 4x^4 + \cdots)\text{.}$

(c)

What is going on here? Where have we seen the coefficients of these polynomials before?

Subsection 2.2.1 Visualizing 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{.}$¹

This approach was inspired by George Pólya's paper “Picture Writing,” in the December, 1956 issue of the American Mathematical Monthly, page 689. While we are taking a somewhat more formal approach than Pólya, it is still completely in the spirit of his work.

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{2.3} \end{align}

Activity 154.

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

Activity 155.

Substitute $x$ for all of $A\text{,}$ $P$ and $B$ (or for the corresponding pictures) in the formula you got in Activity 154 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{2.4} \end{equation}

we would get Formula (2.3). Thus Formula (2.3) and Formula (2.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 (2.3) as describing each individual multiset we can choose, and we interpret Formula (2.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.

Subsection 2.2.2 Picture 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 are really adapting language introduced by George Pólya.

We choose this language because the picture enumerator lists, or enumerates, all the elements of $S$ according to their pictures. Thus Formula (2.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.

Exercise 156.

How would you write down a polynomial in the variable $A$ that says you should take between zero and three apples?

Exercise 157.

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?

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.

Exercise 158.

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.

Subsection 2.2.3 Generating functions

Example 2.2.1.

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.

Solution

We have a polynomial in three variables $A\text{,}$ $P$ and $B$ for this situation:

\begin{equation*} (1+A +A^2 +A^3)(1+P+P^2+P^3)(1+B+B^2+B^3)\text{.} \end{equation*}

Now we substitute $x$ for each of those variables to get

\begin{equation*} (1+x+x^2+x^3)^3 \end{equation*}

Exercise 159.

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 Exercise 157 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?

Hint

For 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{.}$

Exercise 160.

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 Exercise 157 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?

Exercise 161.

We are going to choose a subset of the set $\{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)?

Hint

Consider 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 Exercise 161 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 = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n\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{.}$

Example 2.2.2.

The generating function for the sequence $1, 2, 4, 8, \ldots$ is

\begin{equation*} 1 + 2x + 4x^2 + 8x^3 + \cdots \end{equation*}

which we will see later can be expressed as

\begin{equation*} 1+(2x) + (2x)^2 + (2x)^3 + \cdots = \frac{1}{1-2x}\text{.} \end{equation*}

The sequence $1, 3, 5, 7,\ldots$ has generating function

\begin{equation*} 1+3x + 5x^2 +7x^3 + \cdots = \frac{1+x}{(1-x)^2}\text{.} \end{equation*}

We will soon see why you can write the infinite series in this nice way.

Generating functions for infinite sequences are examples of 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.

In the evolution of our current mathematical terminology, the word function evolved through several meanings, starting with very imprecise meanings and ending with our current rather precise meaning. The terminology “generating function” may be thought of as an example of one of the earlier usages of the term function.

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

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

Activity 162.

Multiply out 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{?}$

Activity 163.

In Activity 162 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 162?

Hint

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

Activity 164.

The point of the Problems 162 and Activity 163 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.

Hint

Write 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*}

Activity 165.

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*}

Hint

How is this problem different from Activity 164? 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 165 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 165. 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.⁴

Technically we should explicitly state these rules and prove that they are all valid for power series multiplication, but it seems like overkill at this point to do so!

Subsection 2.2.5 The extended binomial theorem and multisets

The binomial theorem tells us how to expand the binomial $(1+x)^n\text{:}$

\begin{equation*} (1+x)^n = \binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + \cdots + \binom{n}{n}x^n\text{.} \end{equation*}

This works for any positive integer $n\text{.}$

We will now consider the extended binomial theorem, which tells us what to do if $n$ is a negative integer. In particular, we will see how to expand $(1+x)^{-n} = \frac{1}{(1+x)^n}$ (here taking $n$ positive again).

Although we could use calculus-like tricks to manipulate series directly (and we will demonstrate this in a bit), let's first try to develop the formula combinatorially using generating functions. After all, $(1+x)^n$ is the generating function for the number $k$-element subsets of $[n]$ (you should be able to say why for two good reasons now).

What happens when we instead count the number of $k$-element multisets of $[n]\text{?}$ Remember, we saw in Theorem 1.3.4 that this can be expressed as the binomial coefficeint $\mchoose{n}{k} = \binom{n+k-1}{k}\text{.}$ Let's put this into a generating function.

Activity 166.

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

(b)

Express the generating function in which the coefficient of $x^k$ is the number of $k$-element multisets chosen from $[n]$ as a power of a power series.

Note, it is useful to interpret the coefficient 1 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.

What does this, together with the binomial coefficient for multisets tell you about what this generating function equals?

Hint 1

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

Hint 2

In Theorem 1.3.4 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?

Activity 167.

Compute the product $(1-x)\sum_{k=0}^n x^k = (1-x)(1+x+x^2+\cdots+x^n)\text{.}$ Then compute the product $(1-x)\sum_{k=0}^\infty x^k\text{.}$

Another way to arrive at the conclusion of the previous activity is the following. Set $S = 1 + x + x^2 + \cdots\text{.}$ Then $xS = x + x^2 + x^3 + \cdots\text{.}$ Consider the difference $S - xS\text{.}$ Combining like terms we find $S-xS = (1-x)S = 1\text{,}$ as every power of $x$ cancels except the first. Therefore we find

\begin{equation*} 1 + x + x^2 + \cdots = \frac{1}{1-x}\text{.} \end{equation*}

Activity 168.

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.

We can now put this all together to get a special case of the extended binomial theorem.

Activity 169.

Find a formula for $(1+x)^{-n} = \frac{1}{(1+x)^n}$ as a power series whose coefficients involve binomial coefficients.

Hint 1

The only tricky thing here is that we have $\frac{1}{(1+x)^n}$ instead of $\frac{1}{(1-x)^n}$ which we know something about already. Note that $1 + x = 1 - (-x)\text{.}$

Hint 2

Can you see a way to use Activity 168?

For variety, here is another way you can get to the extended binomial theorem.

Activity 170.

We start with the geometric series

\begin{equation*} \frac{1}{1-x} = 1 + x + x^2 + x^3+ \cdots\text{.} \end{equation*}

(a)

What happens if we take a derivative of both sides? Do this to get a power series for $\frac{1}{(1-x)^2}\text{.}$

Hint

You will get

\begin{equation*} \frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \cdots\text{.} \end{equation*}

(b)

Take another derivative and divide both sides by 2 to get a power series for $\frac{1}{(1-x)^3}\text{.}$ Then write the coefficients in the power series as binomial coefficients (use the factorial formula).

(c)

Prove, by mathematical induction on $n$ that

\begin{equation*} \frac{1}{(1-x)^{n}} = \binom{n-1}{0} + \binom{n}{1}x + \binom{n+1}{2}x^2 + \cdots + \binom{n+k-1}{k}x^k+ \cdots\text{.} \end{equation*}

(d)

Finally, substitute $-x$ for $x$ on both sides.

We used generating functions for multisets to get the extended binomial theorem, but these generating functions are useful in themselves. We close with a few counting problems related to these.

Exercise 171.

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.

Hint 1

Look for a power of a polynomial to get started.

Hint 2

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.

Exercise 172.

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 Exercise 171.

Hint

You should have solved this problem more in general in Exercise 140.

Exercise 173.

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.

Hint

Interpret Exercise 171 in terms of multisets.

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

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

Example 2.2.3.

Find a generating functions for the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}$ with initial conditions $a_1 = 3$ and $a_2 = 13$ (this is the same recurrence relation we solved using the characteristic root technique in Example 1.4.4).

Solution

In general, we have some generating function $f(x) = a_0 + a_1x + a_2x^2 + \cdots\text{.}$ In this case, we know that $a_1 = 3$ and $a_2 = 13\text{;}$ we can find $a_3 = 51$ and, by working backwards, $a_0 = 1\text{.}$ Having these values makes writing the following out a little clearer.

In addition to $f(x)$ we will also consider $3x\cdot f(x)$ and $4x^2 f(x)\text{.}$

\begin{align*} f(x) = \amp 1 + 3x + 13x^2 + 51 x^3 + \cdots \\ 3x f(x) = \amp 3x + 9x^2 + 39x^3 + 153 x^4 + \\ 4x^2 f(x) = \amp 4x^2 + 12x^3 + 52x^4 + 204 x^5 + \end{align*}

Now subtract: $f(x) - 3xf(x) - 4x^2f(x) = 1\text{.}$ That's it. Everything else on the right and side cancels. Why? Well, if you consider the $x^n$ term, it will be $a_n x^n - 3a_{n-1}x^n - 4a_{n-2}x^n\text{.}$ The recurrence relation tells us that the coefficient will be zero!

Simplifying this a bit more, we find $[1- 3x - 4x^2]f(x) = 1\text{,}$ or that the generating function for the sequence is

\begin{equation*} f(x) = \frac{1}{1-3x-4x^2}\text{.} \end{equation*}

Now the question becomes, why does this help? We would like to find a closed formula for $a_n\text{.}$ Right now, we just know that $a_n$ is the coefficient of $x^n$ in the power series for $\frac{1}{1-3x-4x^2}\text{.}$ We will come back to this in the next subsection.

Exercise 174.

Find the generating function for the solutions to the recurrence

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

Of course there is no need to use generating functions to solve recurrences like the ones above, since we could use the characteristic root technique. It gets more interesting when we consider recurrence relations for which the characteristic root technique fails.

Activity 175.

Consider the recurrence relation $a_i=3a_{i-1} + 3^i$ with initial term $a_0 = 1\text{.}$

(a)

Write out the first few terms of the sequence. Then write down the generating series $f(x) = a_0 + a_1x + a_2x^2 + \cdots$ (that is, just substitute in the right values for $a_i$).

(b)

Write out the series for $3x f(x)\text{.}$ Does it make sense why $3x$ is the right thing to multiply by?

(c)

Now subtract $f(x) - 3xf(x)$ to get a series for $(1-3x)\cdot f(x)\text{.}$ Show how this proves that the generating function for $(a_n)$ is

\begin{equation*} f(x) = \frac{1}{(1-3x)^2}\text{.} \end{equation*}

(d)

Now explain why the coefficient of $x^n$ is $\binom{n+1}{1}3^n$ and what that tells us about the sequence $(a_n)\text{.}$

Exercise 176.

Use the previous approach to solve the recurrence relation $a_i=3a_{i-1} + 2^i\text{.}$ Do this in general, for any initial value $a_0\text{.}$

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{.}$

Exercise 177.

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?

The sequence of problems that follows (culminating in Exercise 188) 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.

Apparently Leanardo de Pisa was given the name Fibonacci posthumously. It is a shortening of “son of Bonacci” in Italian.

Exercise 178.

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{.}$ So we have $a_0 = 10\text{,}$ $a_1 = 10\text{,}$ $a_2 = 30\text{,}$ and so on. 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 175, 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.

Exercise 179.

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 Exercise 178. 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 of $n$ months.

Hint

Our recurrence becomes $a_n = a_{n-1} + a_{n-2}\text{,}$ which of course is the Fibonacci recurrence.

Exercise 180.

Use long division on $\dfrac{x}{1-x-x^2}$ and see what pops out.

In the next section we will see how to use the generating functions for these recursions to find closed formulas for the sequence, including a closed formula for the Fibonacci numbers. While we are here though, consider the following example of another reason why having a generating function for the Fibonacci numbers is useful.

Example 2.2.4.

Use generating functions to prove the identity $F_{n+1} = \binom{n}{0} + \binom{n-1}{1} + \binom{n-2}{2} + \cdots $ (note this is a finite sum).

Solution

Start with the generating function for the sequence $1, 1, 2, 3, 5\text{,}$ which we saw in Exercise 179 is

\begin{equation*} \frac{1}{1-x-x^2} = 1 + x + 2x^2 + \cdots + F_{n+1}x^n+ \cdots\text{.} \end{equation*}

Of course we also have

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

and this is almost the same thing. In fact, if we replace $x$ with $x+x^2$ we get the Fibonacci generating function:

\begin{align*} \frac{1}{1-(x+x^2)} = \amp 1 + (x+x^2) + (x+x^2)^2 + \cdots \\ = \amp 1 + x(1+x) + x^2(1+x)^2 + x^3(1+x)^3 + \cdots\text{.} \end{align*}

Now use the binomial theorem on each of the $(1+x)^n$ terms and distribute:

\begin{align*} 1 + x + x^2 + (x^2 +\amp 2x^3 + x^4)\\ + (\amp x^3 + 3x^4 + 3x^5 + x^6)\\ \amp + (x^4 + 4x^5 + 6x^6 + 4x^7 + x^8) + \cdots \text{.} \end{align*}

Look at the coefficient of $x^4\text{,}$ for example. We have $F_5 = 1 + 3 + 1 = \binom{4}{0} + \binom{3}{1} + \binom{2}{2}\text{.}$ It should be clear that this works in general: the coefficient of $x^n$ will be $F_{n+1}$ on the one hand, and $\binom{n}{0} + \binom{n-1}{1} + \binom{n-2}{2}+ \cdots$ on the other.

We also point out that there are other techniques for getting the generating function for a sequence other than the “differencing” we have used above. We illustrate this with an extreme example.

Example 2.2.5.

Find the generating function for the sequence $(a_n)$ where $a_n = \binom{2n}{n}\text{.}$

Solution

We have seen that the power series $1 + x + x^2 + \cdots $ can be written as $\frac{1}{1-x}\text{.}$ Here we wish to find a nice expression for

\begin{equation*} \binom{1}{0} + \binom{2}{1}x + \binom{4}{2}x^2 + \binom{6}{3}x^3+ \cdots\text{.} \end{equation*}

First we note a sort of recurrence: $(n+1)a_{n+1} = (4n+2)a_n\text{.}$ To verify this use the factorial formula for $\binom{n}{k}\text{:}$

\begin{equation*} (n+1)a_{n+1} = (n+1)\binom{2n+2}{n+1} = (n+1)\frac{(2n+2)(2n+1)}{(n+1)!(n+1)!}(2n)! = (4n+2)\binom{2n}{n} \text{.} \end{equation*}

Now, $f(x) = a_0 + a_1x + a_2x^2 + \cdots = \sum_{n=0}^\infty a_nx^n$ has derivative

\begin{equation*} f'(x) = a_1 + 2a_2x + 3a_3x^2 + \cdots = \sum_{n=0}^\infty (n+1)a_{n+1}x^n \end{equation*}

and further

\begin{equation*} xf'(x) = a_1x + 2a_2x^2 + 3a_3x^3 + \cdots = \sum_{n=0}^\infty na_nx^n\text{.} \end{equation*}

Using the recurrence above, we have

\begin{equation*} \sum_{n=0}^\infty (n+1)a_{n+1}x^n = 4\sum_{n=0}^\infty na_nx^n + 2\sum_{n=0}^\infty a_nx^n\text{.} \end{equation*}

This means

\begin{equation*} f'(x) = 4xf'(x) + 2f(x) \end{equation*}

or equivalently

\begin{equation*} \frac{f'(x)}{f(x)} = \frac{2}{1-4x}\text{.} \end{equation*}

Now integrate! We get

\begin{equation*} \ln f(x) = -\frac{1}{2}\ln(1-4x) + c\text{.} \end{equation*}

Since $a_0 =1\text{,}$ it must be $c = 0\text{.}$ Finally then, by exponentiating, we arrive at

\begin{equation*} f(x) = \frac{1}{\sqrt{1-4x}}\text{.} \end{equation*}

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

Activity 181.

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

Activity 182.

In Activity 181 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*}

Activity 183.

In Activity 182 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 Activity 183 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 178 to Exercise 174. However you have to be able to factor the quadratic polynomials that are in the denominators of your generating functions.

Example 2.2.6.

Let's return to our familiar recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}$ with initial terms $a_1 = 3$ and $a_2 = 13\text{.}$

In Example 1.4.4 we used the characteristic root technique to find the closed formula

\begin{equation*} a_n = \frac{4}{5} 4^n + \frac{1}{5} (-1)^n \text{.} \end{equation*}

In Example 2.2.3 we found that the generating function for the sequence was

\begin{equation*} f(x) = \frac{1}{1-3x - 4x^2}\text{.} \end{equation*}

We can use partial fractions to reconcile these two results.

Note that the denominator factors as $(1+x)(1-4x)\text{.}$ We write

\begin{equation*} \frac{1}{1-3x-4x^2} = \frac{c}{1+x}+\frac{d}{1-4x} \end{equation*}

and solve for $c$ and $d\text{.}$ This is done by finding a common denominator and equating the numerators to get

\begin{equation*} 1 = c(1-4x) + d(1+x) \end{equation*}

Note that if $x = -1$ this gives use $1 = 5c$ so $c = \frac{1}{5}\text{.}$ Similarly, if $x = \frac{1}{4}$ we find $1 = \frac{5}{4}d$ so $d = \frac{4}{5}\text{.}$ (These constants should look familiar.)

So what? The generating function for $a_n$ can now be expressed as the sum of two generating functions: $\frac{1/5}{1+x}$ and $\frac{4/5}{1-4x}\text{.}$ What's more, these generating functions have nice power series:

\begin{equation*} \frac{1/5}{1+x} = \frac{1}{5}\left( 1-x+x^2-x^3+\cdots +(-1)^nx^n+\cdots\right)\text{;} \end{equation*}

\begin{equation*} \frac{4/5}{(1-4x)} = \frac{4}{5} \left(1+4x + 16x^2 + \cdots + 4^nx^n+ \cdots \right)\text{.} \end{equation*}

Both of these were found by substituting a value (either $-x$ or $4x$) into the power series for $\frac{1}{1-x}\text{.}$

Since $a_n$ is the coefficient of $x^n\text{,}$ we get

\begin{equation*} a_n = \frac{1}{5}(-1)^n + \frac{4}{5}4^n \end{equation*}

as expected.

Exercise 184.

Use the method of partial fractions to convert the generating function $\frac{10}{1-x-2x^2}$ from Exercise 178 into the sum of two nicer generating functions. Use this to find a formula for $a_n\text{.}$

Exercise 185.

Find the value of $a_{40}$ in the power series

\begin{equation*} \frac{x-2}{3-4x +x^2} = a_0 + a_1x + a_2x^2 + \cdots + a_{40}x^{40}+\cdots. \end{equation*}

Hint

$3-4x+x^2 = (1-x)(3-x)\text{.}$ The power series for $\frac{A}{1-x}$ should be easy to express, but $\frac{B}{3-x}$ might make more sense written as $\frac{B/3}{1-\frac{1}{3}x}\text{.}$

Exercise 186.

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{.}$

Exercise 187.

Use the factors you found in Exercise 186 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.⁶ 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.

We use the words roots and solutions interchangeably.

Exercise 188.

(a)

Use the partial fractions decomposition you found in Exercise 187 to write the generating function you found in Exercise 179 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 Exercise 187 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 5 go away.

Hint

Think about how the binomial theorem might help you.

(e)

As a challenge (which the authors have 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 Binet for the Fibonacci numbers yields integers.

Activity 189.

Solve the recurrence $a_n= 4a_{n-1} - 4a_{n-2}\text{.}$ You did this already in Exercise 89 using the characteristic root technique, but there you had to be careful of the repeated root. How does that manifest itself here?

The point of the previous exercise is to notice how generating functions illustrate where the extra factor of $n$ comes from in the general form $a_n = \alpha r^n + \beta n r^n$ you get for a closed formula when using the characteristic root technique on a recurrence that gives you a repeated root $r\text{.}$ For any $r\text{,}$ we have the power series

\begin{equation*} \frac{1}{(1-rx)^2} = 1 + 2(rx) + 3(rx)^2 + \cdots + (n+1)(rx)^n + \cdots\text{,} \end{equation*}

using the extended binomial theorem and substituting $rx$ for $x\text{.}$ The coefficient of $x^n$ is then $(n+1)r^n = r^n + nr^n\text{.}$

Catalan Numbers.

Exercise 190.

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)

Use $C_0 = 1$ and compute $C_1, C_2, C_3, C_4, C_5\text{.}$

(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{P(r,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*}

Summary of Generating Functions.

Sequence:	Power Series:	Generating Function:
$1, 1, 1, \ldots$	$1+x+x^2+x^3+\cdots$	\begin{equation} \displaystyle\frac{1}{1-x} \end{equation}
$1, 2, 4, 8,\ldots$	$1+2x+(2x)^2+(2x)^3+\cdots$	\begin{equation} \displaystyle\frac{1}{1-2x} \end{equation}
$1, -1, 1, -1, \ldots$	$1-x+x^2-x^3+\cdots$	\begin{equation} \displaystyle\frac{1}{1+x} \end{equation}
$0, 3, 3^2, 3^3,\ldots$	$3x+(3x)^2+(3x)^3+\cdots$	\begin{equation} \displaystyle\frac{3x}{1-3x} \end{equation}
$1, a, a^2,\ldots \ldots$	$1+ax+(ax)^2+\cdots$	\begin{equation} \displaystyle\frac{1}{1-ax} \end{equation}
$1, 2, 3, 4, \ldots$	$1+2x+3x^2+4x^3+\cdots$	\begin{equation} \displaystyle\frac{1}{(1-x)^2} \end{equation}
$0, 1, 2, 3, \ldots$	$x+2x^2+3x^3+\cdots$	\begin{equation} \displaystyle\frac{x}{(1-x)^2} \end{equation}
$1,0, 2, 0, 3,0, \ldots$	$1+2x^2+3x^4+\cdots$	\begin{equation} \displaystyle\frac{1}{(1-x^2)^2} \end{equation}
$\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \ldots$	$\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots$	\begin{equation} \displaystyle(1+x)^n \end{equation}
$\binom{2}{2}, \binom{3}{2}, \binom{4}{2}, \ldots$	$\binom{2}{2}+\binom{3}{2}x+\binom{4}{2}x^2+\cdots$	\begin{equation} \displaystyle\frac{1}{(1-x)^3} \end{equation}
$1, -2, 3,-4, \ldots$	$1-2x+3x^2-4x^3+\cdots$	\begin{equation} \displaystyle\frac{1}{(1+x)^2} \end{equation}
$1, 2(2), 3(2^2), \ldots$	$1+2(2x)+3(2x)^2+\cdots$	\begin{equation} \displaystyle\frac{1}{(1-2x)^2} \end{equation}
$1, 1, \frac{1}{2!}, \frac{1}{3!}, \ldots$	$1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots$	\begin{equation} e^x \end{equation}

	\(x\)	\(x^2\)	\(x^3\)	\(x^4\)	\(x^5\)	\(x^6\)
\(x\)
\(x^2\)
\(x^3\)
\(x^4\)
\(x^5\)
\(x^6\)

Sequence:	Power Series:	Generating Function:
\(1, 1, 1, \ldots\)	\(1+x+x^2+x^3+\cdots\)	\begin{equation} \displaystyle\frac{1}{1-x} \end{equation}
\(1, 2, 4, 8,\ldots\)	\(1+2x+(2x)^2+(2x)^3+\cdots\)	\begin{equation} \displaystyle\frac{1}{1-2x} \end{equation}
\(1, -1, 1, -1, \ldots\)	\(1-x+x^2-x^3+\cdots\)	\begin{equation} \displaystyle\frac{1}{1+x} \end{equation}
\(0, 3, 3^2, 3^3,\ldots\)	\(3x+(3x)^2+(3x)^3+\cdots\)	\begin{equation} \displaystyle\frac{3x}{1-3x} \end{equation}
\(1, a, a^2,\ldots \ldots\)	\(1+ax+(ax)^2+\cdots\)	\begin{equation} \displaystyle\frac{1}{1-ax} \end{equation}
\(1, 2, 3, 4, \ldots\)	\(1+2x+3x^2+4x^3+\cdots\)	\begin{equation} \displaystyle\frac{1}{(1-x)^2} \end{equation}
\(0, 1, 2, 3, \ldots\)	\(x+2x^2+3x^3+\cdots\)	\begin{equation} \displaystyle\frac{x}{(1-x)^2} \end{equation}
\(1,0, 2, 0, 3,0, \ldots\)	\(1+2x^2+3x^4+\cdots\)	\begin{equation} \displaystyle\frac{1}{(1-x^2)^2} \end{equation}
\(\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \ldots\)	\(\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots\)	\begin{equation} \displaystyle(1+x)^n \end{equation}
\(\binom{2}{2}, \binom{3}{2}, \binom{4}{2}, \ldots\)	\(\binom{2}{2}+\binom{3}{2}x+\binom{4}{2}x^2+\cdots\)	\begin{equation} \displaystyle\frac{1}{(1-x)^3} \end{equation}
\(1, -2, 3,-4, \ldots\)	\(1-2x+3x^2-4x^3+\cdots\)	\begin{equation} \displaystyle\frac{1}{(1+x)^2} \end{equation}
\(1, 2(2), 3(2^2), \ldots\)	\(1+2(2x)+3(2x)^2+\cdots\)	\begin{equation} \displaystyle\frac{1}{(1-2x)^2} \end{equation}
\(1, 1, \frac{1}{2!}, \frac{1}{3!}, \ldots\)	\(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\)	\begin{equation} e^x \end{equation}