Generating Functions

Section 6.1 Generating Functions

There is an extremely powerful tool in discrete mathematics used to manipulate sequences called the generating function. The idea is this: instead of an infinite sequence (for example:

2, 3, 5, 8, 12, \dots

) we look at a single function which encodes the sequence. But not a function that gives the

n

th term as output. Instead, a function whose power series (like from calculus) “displays” the terms of the sequence. So for example, we would look at the power series

2 + 3 x + 5 x^{2} + 8 x^{3} + 12 x^{4} + \dots

which displays the sequence

2, 3, 5, 8, 12, \dots

as coefficients.

🔗

An infinite power series is simply an infinite sum of terms of the form

c_{n} x^{n}

were

c_{n}

is some constant. So we might write a power series like this:

\sum_{k = 0}^{\infty} c_{k} x^{k} .

or expanded like this

c_{0} + c_{1} x + c_{2} x^{2} + c_{3} x^{3} + c_{4} x^{4} + c_{5} x^{5} + \dots .

🔗

When viewed in the context of generating functions, we call such a power series a generating series. The generating series generates the sequence

c_{0}, c_{1}, c_{2}, c_{3}, c_{4}, c_{5}, \dots .

🔗

In other words, the sequence generated by a generating series is simply the sequence of coefficients of the infinite polynomial.

🔗

Example 6.1.1.

What sequence is represented by the generating series

3 + 8 x^{2} + x^{3} + \frac{x^{5}}{7} + 100 x^{6} + \dots ?

🔗

Solution.

We just read off the coefficients of each

x^{n}

term. So

a_{0} = 3

since the coefficient of

x^{0}

is 3 (

x^{0} = 1

so this is the constant term). What is

a_{1} ?

It is NOT 8, since 8 is the coefficient of

x^{2},

so 8 is the term

a_{2}

of the sequence. To find

a_{1}

we need to look for the coefficient of

x^{1}

which in this case is 0. So

a_{1} = 0 .

Continuing, we have

a_{2} = 8,

a_{3} = 1,

a_{4} = 0,

and

a_{5} = \frac{1}{7} .

So we have the sequence

3, 0, 8, 1, 0, \frac{1}{7}, 100, \dots .

🔗

Note that when discussing generating functions, we always start our sequence with

a_{0} .

🔗

Now you might very naturally ask why we would do such a thing. One reason is that encoding a sequence with a power series helps us keep track of which term is which in the sequence. For example, if we write the sequence

1, 3, 4, 6, 9, \dots, 24, 41, \dots

it is impossible to determine which term

24

is (even if we agreed that the first term was supposed to be

a_{0}

). However, if we wrote the generating series instead, we would have

1 + 3 x + 4 x^{2} + 6 x^{3} + 9 x^{4} + \dots + 24 x^{17} + 41 x^{18} + \dots .

Now it is clear that 24 is the 17th term of the sequence (that is,

a_{17} = 24

). Of course to get this benefit we could have displayed our sequence in any number of ways, perhaps

1_{0} 3_{1} 4_{2} 6_{3} 9_{4} \dots 24_{17} 41_{18} \dots,

but we do not do this. The reason is that the generating series looks like an ordinary power series (although we are interpreting it differently) so we can do things with it that we ordinarily do with power series such as write down what it converges to.

🔗

For example, from calculus we know that the power series

1 + x + \frac{x^{2}}{2} + \frac{x^{3}}{6} + \frac{x^{4}}{24} + \dots + \frac{x^{n}}{n!} + \dots

converges to the function

e^{x} .

So we can use

e^{x}

as a way of talking about the sequence of coefficients of the power series for

e^{x} .

When we write down a nice compact function which has an infinite power series that we view as a generating series, then we call that function a generating function. In this example, we would say

1, 1, \frac{1}{2}, \frac{1}{6}, \frac{1}{24}, \dots, \frac{1}{n!}, \dots has generating function e^{x} .

🔗

Subsection Building Generating Functions

The

e^{x}

example is very specific. We have a rather odd sequence, and the only reason we know its generating function is because we happen to know the Taylor series for

e^{x} .

Our goal now is to gather some tools to build the generating function of a particular given sequence.

🔗

Let’s see what the generating functions are for some very simple sequences. The simplest of all: 1, 1, 1, 1, 1, …. What does the generating series look like? It is simply

1 + x + x^{2} + x^{3} + x^{4} + \dots .

Now, can we find a closed formula for this power series? Yes! This particular series is really just a geometric series with common ratio

x .

So if we use our “multiply, shift and subtract” technique from Section 4.4, we have

\begin{aligned} S & = 1 + x + x^{2} + x^{3} + \dots \\ \underset{―}{- x S} & \underset{―}{= x + x^{2} + x^{3} + x^{4} + \dots} \\ (1 - x) S & = 1 \end{aligned}

🔗

Therefore we see that

1 + x + x^{2} + x^{3} \dots = \frac{1}{1 - x} .

🔗

You might remember from calculus that this is only true on the interval of convergence for the power series, in this case when

| x | < 1 .

That is true for us, but we don’t care. We are never going to plug anything in for

x,

so as long as there is some value of

x

for which the generating function and generating series agree, we are happy. And in this case we are happy.

🔗

$1, 1, 1, \dots$ .

The generating function for

1, 1, 1, 1, 1, 1, \dots

\frac{1}{1 - x}

🔗

Let’s use this basic generating function to find generating functions for more sequences. What if we replace

x

- x .

We get

\frac{1}{1 + x} = 1 - x + x^{2} - x^{3} + \dots which generates 1, - 1, 1, - 1, \dots .

🔗

If we replace

x

3 x

we get

\frac{1}{1 - 3 x} = 1 + 3 x + 9 x^{2} + 27 x^{3} + \dots which generates 1, 3, 9, 27, \dots .

🔗

By replacing the

x

\frac{1}{1 - x}

we can get generating functions for a variety of sequences, but not all. For example, you cannot plug in anything for

x

to get the generating function for

2, 2, 2, 2, \dots .

However, we are not lost yet. Notice that each term of

2, 2, 2, 2, \dots

is the result of multiplying the terms of

1, 1, 1, 1, \dots

by the constant 2. So multiply the generating function by 2 as well.

\frac{2}{1 - x} = 2 + 2 x + 2 x^{2} + 2 x^{3} + \dots which generates 2, 2, 2, 2, \dots .

🔗

Similarly, to find the generating function for the sequence

3, 9, 27, 81, \dots,

we note that this sequence is the result of multiplying each term of

1, 3, 9, 27, \dots

by 3. Since we have the generating function for

1, 3, 9, 27, \dots

we can say

\frac{3}{1 - 3 x} = 3 \cdot 1 + 3 \cdot 3 x + 3 \cdot 9 x^{2} + 3 \cdot 27 x^{3} + \dots which generates 3, 9, 27, 81, \dots .

🔗

What about the sequence

2, 4, 10, 28, 82, \dots ?

Here the terms are always 1 more than powers of 3. That is, we have added the sequences

1, 1, 1, 1, \dots

and

1, 3, 9, 27, \dots

term by term. Therefore we can get a generating function by adding the respective generating functions:

\begin{aligned} 2 + 4 x + 10 x^{2} + 28 x^{3} + \dots & = (1 + 1) + (1 + 3) x + (1 + 9) x^{2} + (1 + 27) x^{3} + \dots \\ = 1 + x + x^{2} + x^{3} + \dots + 1 + 3 x + 9 x^{2} + 27 x^{3} + \dots \\ = \frac{1}{1 - x} + \frac{1}{1 - 3 x} \end{aligned}

🔗

The fun does not stop there: if we replace

x

in our original generating function by

x^{2}

we get

\frac{1}{1 - x^{2}} = 1 + x^{2} + x^{4} + x^{6} \dots which generates 1, 0, 1, 0, 1, 0, \dots .

🔗

How could we get

0, 1, 0, 1, 0, 1, \dots ?

Start with the previous sequence and shift it over by 1. But how do you do this? To see how shifting works, let’s first try to get the generating function for the sequence

0, 1, 3, 9, 27, \dots .

We know that

\frac{1}{1 - 3 x} = 1 + 3 x + 9 x^{2} + 27 x^{3} + \dots .

To get the zero out front, we need the generating series to look like

x + 3 x^{2} + 9 x^{3} + 27 x^{4} + \dots

(so there is no constant term). Multiplying by

x

has this effect. So the generating function for

0, 1, 3, 9, 27, \dots

\frac{x}{1 - 3 x} .

This will also work to get the generating function for

0, 1, 0, 1, 0, 1, \dots :

\frac{x}{1 - x^{2}} = x + x^{3} + x^{5} + \dots which generates 0, 1, 0, 1, 0, 1 \dots .

🔗

What if we add the sequences

1, 0, 1, 0, 1, 0, \dots

and

0, 1, 0, 1, 0, 1, \dots

term by term? We should get

1, 1, 1, 1, 1, 1 \dots .

What happens when we add the generating functions? It works (try it)!

\frac{1}{1 - x^{2}} + \frac{x}{1 - x^{2}} = \frac{1}{1 - x} .

🔗

Here’s a sneaky one: what happens if you take the derivative of

\frac{1}{1 - x} ?

We get

\frac{1}{(1 - x)^{2}} .

On the other hand, if we differentiate term by term in the power series, we get

(1 + x + x^{2} + x^{3} + \dots)^{'} = 1 + 2 x + 3 x^{2} + 4 x^{3} + \dots

which is the generating series for

1, 2, 3, 4, \dots .

This says

🔗

$1, 2, 3, \dots$ .

The generating function for

1, 2, 3, 4, 5, \dots

\frac{1}{(1 - x)^{2}} .

🔗

Take a second derivative:

\frac{2}{(1 - x)^{3}} = 2 + 6 x + 12 x^{2} + 20 x^{3} + \dots .

\frac{1}{(1 - x)^{3}} = 1 + 3 x + 6 x^{2} + 10 x^{3} + \dots

is a generating function for the triangular numbers,

1, 3, 6, 10 \dots

(although here we have

a_{0} = 1

while

T_{0} = 0

usually).

🔗

Subsection Differencing

We have seen how to find generating functions from

\frac{1}{1 - x}

using multiplication (by a constant or by

x

), substitution, addition, and differentiation. To use each of these, you must notice a way to transform the sequence

1, 1, 1, 1, 1 \dots

into your desired sequence. This is not always easy. It is also not really the way we have analyzed sequences. One thing we have considered often is the sequence of differences between terms of a sequence. This will turn out to be helpful in finding generating functions as well. The sequence of differences is often simpler than the original sequence. So if we know a generating function for the differences, we would like to use this to find a generating function for the original sequence.

🔗

For example, consider the sequence

2, 4, 10, 28, 82, \dots .

How could we move to the sequence of first differences:

2, 6, 18, 54, \dots ?

We want to subtract 2 from the 4, 4 from the 10, 10 from the 28, and so on. So if we subtract (term by term) the sequence

0, 2, 4, 10, 28, \dots

from

2, 4, 10, 28 \dots,

we will be set. We can get the generating function for

0, 2, 4, 10, 28, \dots

from the generating function for

2, 4, 10, 28 \dots

by multiplying by

x .

Use

A

to represent the generating function for

2, 4, 10, 28, 82, \dots

Then:

\begin{aligned} A & = 2 + 4 x + 10 x^{2} + 28 x^{3} + 82 x^{4} + \dots \\ \underset{―}{- x A} & \underset{―}{= 0 + 2 x + 4 x^{2} + 10 x^{3} + 28 x^{4} + 82 x^{5} + \dots} \\ (1 - x) A & = 2 + 2 x + 6 x^{2} + 18 x^{3} + 54 x^{4} + \dots \end{aligned}

🔗

While we don’t get exactly the sequence of differences, we do get something close. In this particular case, we already know the generating function

A

(we found it in the previous section) but most of the time we will use this differencing technique to find

A :

if we have the generating function for the sequence of differences, we can then solve for

A .

🔗

Example 6.1.2.

Find a generating function for

1, 3, 5, 7, 9, \dots .

🔗

Solution.

Notice that the sequence of differences is constant. We know how to find the generating function for any constant sequence. So denote the generating function for

1, 3, 5, 7, 9, \dots

A .

We have

\begin{aligned} A & = 1 + 3 x + 5 x^{2} + 7 x^{3} + 9 x^{4} + \dots \\ \underset{―}{- x A} & \underset{―}{= 0 + x + 3 x^{2} + 5 x^{3} + 7 x^{4} + 9 x^{5} + \dots} \\ (1 - x) A & = 1 + 2 x + 2 x^{2} + 2 x^{3} + 2 x^{4} + \dots \end{aligned}

🔗

We know that

2 x + 2 x^{2} + 2 x^{3} + 2 x^{4} + \dots = \frac{2 x}{1 - x} .

Thus

(1 - x) A = 1 + \frac{2 x}{1 - x} .

🔗

Now solve for

A :

A = \frac{1}{1 - x} + \frac{2 x}{(1 - x)^{2}} = \frac{1 + x}{(1 - x)^{2}} .

🔗

Does this make sense? Before we simplified the two fractions into one, we were adding the generating function for the sequence

1, 1, 1, 1, \dots

to the generating function for the sequence

0, 2, 4, 6, 8, 10, \dots

(remember

\frac{1}{(1 - x)^{2}}

generates

1, 2, 3, 4, 5, \dots,

multiplying by

2 x

shifts it over, putting the zero out front, and doubles each term). If we add these term by term, we get the correct sequence

1, 3, 5, 7, 9, \dots .

🔗

Now that we have a generating function for the odd numbers, we can use that to find the generating function for the squares:

🔗

Example 6.1.3.

Find the generating function for

1, 4, 9, 16, \dots .

Note we take

1 = a_{0} .

🔗

Solution.

Again we call the generating function for the sequence

A .

Using differencing:

\begin{aligned} A & = 1 + 4 x + 9 x^{2} + 16 x^{3} + \dots \\ \underset{―}{- x A} & \underset{―}{= 0 + x + 4 x^{2} + 9 x^{3} + 16 x^{4} + \dots} \\ (1 - x) A & = 1 + 3 x + 5 x^{2} + 7 x^{3} + \dots \end{aligned}

🔗

Since

1 + 3 x + 5 x^{2} + 7 x^{3} + \dots = \frac{1 + x}{(1 - x)^{2}}

we have

A = \frac{1 + x}{(1 - x)^{3}} .

🔗

In each of the examples above, we found the difference between consecutive terms which gave us a sequence of differences for which we knew a generating function. We can generalize this to more complicated relationships between terms of the sequence. For example, if we know that the sequence satisfies the recurrence relation

a_{n} = 3 a_{n - 1} - 2 a_{n - 2} ?

In other words, if we take a term of the sequence and subtract 3 times the previous term and then add 2 times the term before that, we get 0 (since

a_{n} - 3 a_{n - 1} + 2 a_{n - 2} = 0

). That will hold for all but the first two terms of the sequence. So after the first two terms, the sequence of results of these calculations would be a sequence of 0’s, for which we definitely know a generating function.

🔗

Example 6.1.4.

The sequence

1, 3, 7, 15, 31, 63, \dots

satisfies the recurrence relation

a_{n} = 3 a_{n - 1} - 2 a_{n - 2} .

Find the generating function for the sequence.

🔗

Solution.

Call the generating function for the sequence

A .

We have

\begin{aligned} A & = 1 + 3 x + 7 x^{2} + 15 x^{3} + 31 x^{4} + \dots + a_{n} x^{n} + \dots \\ - 3 x A & = 0 - 3 x - 9 x^{2} - 21 x^{3} - 45 x^{4} - \dots - 3 a_{n - 1} x^{n} - \dots \\ \underset{―}{+ 2 x^{2} A_{}^{^{}}} & \underset{―}{= 0 + 0 x + 2 x^{2} + 6 x^{3} + 14 x^{4} + \dots + 2 a_{n - 2} x^{n} + \dots} \\ (1 - 3 x + 2 x^{2}) A & = 1 \end{aligned}

🔗

We multiplied

A

- 3 x

which shifts every term over one spot and multiplies them by

- 3 .

On the third line, we multiplied

A

2 x^{2},

which shifted every term over two spots and multiplied them by 2. When we add up the corresponding terms, we are taking each term, subtracting 3 times the previous term, and adding 2 times the term before that. This will happen for each term after

a_{1}

because

a_{n} - 3 a_{n - 1} + 2 a_{n - 2} = 0 .

In general, we might have two terms from the beginning of the generating series, although in this case the second term happens to be 0 as well.

🔗

Now we just need to solve for

A :

A = \frac{1}{1 - 3 x + 2 x^{2}} .

🔗

Subsection Multiplication and Partial Sums

What happens to the sequences when you multiply two generating functions? Let’s see:

A = a_{0} + a_{1} x + a_{2} x^{2} + \dots

and

B = b_{0} + b_{1} x + b_{2} x^{2} + \dots .

To multiply

A

and

B,

we need to do a lot of distributing (infinite FOIL?) but keep in mind we will group like terms and only need to write down the first few terms to see the pattern. The constant term is

a_{0} b_{0} .

The coefficient of

x

a_{0} b_{1} + a_{1} b_{0} .

And so on. We get:

A B = a_{0} b_{0} + (a_{0} b_{1} + a_{1} b_{0}) x + (a_{0} b_{2} + a_{1} b_{1} + a_{2} b_{0}) x^{2} + (a_{0} b_{3} + a_{1} b_{2} + a_{2} b_{1} + a_{3} b_{0}) x^{3} + \dots .

🔗

Example 6.1.5.

“Multiply” the sequence

1, 2, 3, 4, \dots

by the sequence

1, 2, 4, 8, 16, \dots .

🔗

Solution.

The new constant term is just

1 \cdot 1 .

The next term will be

1 \cdot 2 + 2 \cdot 1 = 4 .

The next term:

1 \cdot 4 + 2 \cdot 2 + 3 \cdot 1 = 11 .

One more:

1 \cdot 8 + 2 \cdot 4 + 3 \cdot 2 + 4 \cdot 1 = 26 .

The resulting sequence is

1, 4, 11, 26, 57, \dots .

🔗

Since the generating function for

1, 2, 3, 4, \dots

\frac{1}{(1 - x)^{2}}

and the generating function for

1, 2, 4, 8, 16, \dots

\frac{1}{1 - 2 x},

we have that the generating function for

1, 4, 11, 26, 57, \dots

\frac{1}{(1 - x)^{2} (1 - 2 x)}

🔗

Consider the special case when you multiply a sequence by

1, 1, 1, \dots .

For example, multiply

1, 1, 1, \dots

1, 2, 3, 4, 5 \dots .

The first term is

1 \cdot 1 = 1 .

Then

1 \cdot 2 + 1 \cdot 1 = 3 .

Then

1 \cdot 3 + 1 \cdot 2 + 1 \cdot 1 = 6 .

The next term will be 10. We are getting the triangular numbers. More precisely, we get the sequence of partial sums of

1, 2, 3, 4, 5, \dots .

In terms of generating functions, we take

\frac{1}{1 - x}

(generating

1, 1, 1, 1, 1 \dots

) and multiply it by

\frac{1}{(1 - x)^{2}}

(generating

1, 2, 3, 4, 5, \dots

) and this gives

\frac{1}{(1 - x)^{3}} .

This should not be a surprise as we found the same generating function for the triangular numbers earlier.

🔗

The point is, if you need to find a generating function for the sum of the first

n

terms of a particular sequence, and you know the generating function for that sequence, you can multiply it by

\frac{1}{1 - x} .

To go back from the sequence of partial sums to the original sequence, you look at the sequence of differences. When you get the sequence of differences you end up multiplying by

1 - x,

or equivalently, dividing by

\frac{1}{1 - x} .

Multiplying by

\frac{1}{1 - x}

gives partial sums, dividing by

\frac{1}{1 - x}

gives differences.

🔗

Subsection Solving Recurrence Relations with Generating Functions

We conclude with an example of one of the many reasons studying generating functions is helpful. We can use generating functions to solve recurrence relations.

🔗

Example 6.1.6.

Solve the recurrence relation

a_{n} = 3 a_{n - 1} - 2 a_{n - 2}

with initial conditions

a_{0} = 1

and

a_{1} = 3 .

🔗

Solution.

We saw in an example above that this recurrence relation gives the sequence

1, 3, 7, 15, 31, 63, \dots

which has generating function

\frac{1}{1 - 3 x + 2 x^{2}} .

We did this by calling the generating function

A

and then computing

A - 3 x A + 2 x^{2} A

which was just 1, since every other term canceled out.

🔗

But how does knowing the generating function help us? First, break up the generating function into two simpler ones. For this, we can use partial fraction decomposition. Start by factoring the denominator:

\frac{1}{1 - 3 x + 2 x^{2}} = \frac{1}{(1 - x) (1 - 2 x)} .

🔗

Partial fraction decomposition tells us that we can write this faction as the sum of two fractions (we decompose the given fraction):

\frac{1}{(1 - x) (1 - 2 x)} = \frac{a}{1 - x} + \frac{b}{1 - 2 x} ~~ for some constants a and b .

🔗

To find

a

and

b

we add the two decomposed fractions using a common denominator. This gives

\frac{1}{(1 - x) (1 - 2 x)} = \frac{a (1 - 2 x) + b (1 - x)}{(1 - x) (1 - 2 x)} .

1 = a (1 - 2 x) + b (1 - x) .

🔗

This must be true for all values of

x .

x = 1,

then the equation becomes

1 = - a

a = - 1 .

When

x = \frac{1}{2}

we get

1 = b / 2

b = 2 .

This tells us that we can decompose the fraction like this:

\frac{1}{(1 - x) (1 - 2 x)} = \frac{- 1}{1 - x} + \frac{2}{1 - 2 x} .

🔗

This completes the partial fraction decomposition. Notice that these two fractions are generating functions we know. In fact, we should be able to expand each of them.

\frac{- 1}{1 - x} = - 1 - x - x^{2} - x^{3} - x^{4} - \dots which generates - 1, - 1, - 1, - 1, - 1, \dots .

\frac{2}{1 - 2 x} = 2 + 4 x + 8 x^{2} + 16 x^{3} + 32 x^{4} + \dots which generates 2, 4, 8, 16, 32, \dots .

🔗

We can give a closed formula for the

n

th term of each of these sequences. The first is just

a_{n} = - 1 .

The second is

a_{n} = 2^{n + 1} .

The sequence we are interested in is just the sum of these, so the solution to the recurrence relation is

a_{n} = 2^{n + 1} - 1 .

🔗

We can now add generating functions to our list of methods for solving recurrence relations.

🔗

Exercises Exercises

1.

Find the generating function for each of the following sequences by relating them back to a sequence with known generating function.

$4, 4, 4, 4, 4, \dots .$

🔗
$2, 4, 6, 8, 10, \dots .$

🔗
$0, 0, 0, 2, 4, 6, 8, 10, \dots .$

🔗
$1, 5, 25, 125, \dots .$

🔗
$1, - 3, 9, - 27, 81, \dots .$

🔗
$1, 0, 5, 0, 25, 0, 125, 0, \dots .$

🔗
$0, 1, 0, 0, 2, 0, 0, 3, 0, 0, 4, 0, 0, 5, \dots .$

🔗

🔗

2.

Find the sequence generated by the following generating functions:

$\frac{4 x}{1 - x} .$

🔗
$\frac{1}{1 - 4 x} .$

🔗
$\frac{x}{1 + x} .$

🔗
$\frac{3 x}{(1 + x)^{2}} .$

🔗
$\frac{1 + x + x^{2}}{(1 - x)^{2}}$ (Hint: multiplication).

🔗

🔗

3.

Show how you can get the generating function for the triangular numbers in three different ways:

Take two derivatives of the generating function for $1, 1, 1, 1, 1, \dots$
🔗

🔗
Use differencing.
🔗

🔗
Multiply two known generating functions.
🔗

🔗

🔗

4.

Use differencing to find the generating function for

4, 5, 7, 10, 14, 19, 25, \dots .

🔗

5.

Find a generating function for the sequence with recurrence relation

a_{n} = 3 a_{n - 1} - a_{n - 2}

with initial terms

a_{0} = 1

and

a_{1} = 5 .

🔗

6.

Use the recurrence relation for the Fibonacci numbers to find the generating function for the Fibonacci sequence.

🔗

7.

Use multiplication to find the generating function for the sequence of partial sums of Fibonacci numbers,

S_{0}, S_{1}, S_{2}, \dots

where

S_{0} = F_{0},

S_{1} = F_{0} + F_{1},

S_{2} = F_{0} + F_{1} + F_{2},

S_{3} = F_{0} + F_{1} + F_{2} + F_{3}

and so on.

🔗

8.

Find the generating function for the sequence with closed formula

a_{n} = 2 (5^{n}) + 7 (- 3)^{n} .

🔗

9.

Find a closed formula for the

n

th term of the sequence with generating function

\frac{3 x}{1 - 4 x} + \frac{1}{1 - x} .

🔗

10.

Find

a_{7}

for the sequence with generating function

\frac{2}{(1 - x)^{2}} \cdot \frac{x}{1 - x - x^{2}} .

🔗

Hint.

You should “multiply” the two sequences.

🔗

11.

Explain how we know that

\frac{1}{(1 - x)^{2}}

is the generating function for

1, 2, 3, 4, \dots .

🔗

12.

Starting with the generating function for

1, 2, 3, 4, \dots,

find a generating function for each of the following sequences.

$1, 0, 2, 0, 3, 0, 4, \dots .$

🔗
$1, - 2, 3, - 4, 5, - 6, \dots .$

🔗
$0, 3, 6, 9, 12, 15, 18, \dots .$

🔗
$0, 3, 9, 18, 30, 45, 63, \dots .$ (Hint: relate this sequence to the previous one.)

🔗

🔗

13.

You may assume that

1, 1, 2, 3, 5, 8, \dots

has generating function

\frac{1}{1 - x - x^{2}}

(because it does). Use this fact to find the sequence generated by each of the following generating functions.

$\frac{x^{2}}{1 - x - x^{2}} .$

🔗
$\frac{1}{1 - x^{2} - x^{4}} .$

🔗
$\frac{1}{1 - 3 x - 9 x^{2}} .$

🔗
$\frac{1}{(1 - x - x^{2}) (1 - x)} .$

🔗

🔗

14.

Find the generating function for the sequence

1, - 2, 4, - 8, 16, \dots .

🔗

15.

Find the generating function for the sequence

1, 1, 1, 2, 3, 4, 5, 6, \dots .

🔗

16.

Suppose

A

is the generating function for the sequence

3, 5, 9, 15, 23, 33, \dots .

Find a generating function (in terms of $A$ ) for the sequence of differences between terms.
🔗

🔗
Write the sequence of differences between terms and find a generating function for it (without referencing $A$ ).
🔗

🔗
Use your answers to parts (a) and (b) to find the generating function for the original sequence.
🔗

🔗

🔗

You have attempted 1 of 1 activities on this page.

🔗

Prev Top Next

Section 6.1 Generating Functions

Example 6.1.1.

Subsection Building Generating Functions

1,1,1,….

1,2,3,….

Subsection Differencing

Example 6.1.2.

Example 6.1.3.

Example 6.1.4.

Subsection Multiplication and Partial Sums

Example 6.1.5.

Subsection Solving Recurrence Relations with Generating Functions

Example 6.1.6.

Exercises Exercises

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

$1, 1, 1, \dots$ .

$1, 2, 3, \dots$ .