AI Tutor
Back to Discrete Mathematics: An Open Introduction

Generating Functions

Encoding a sequence as the coefficients of a power series, so operations on the function read off closed formulas and recurrence solutions.

Discrete Mathematics: An Open Introduction, Generating Functions

Status
FlagsLoading your progress…

11 exercises

Exercise 1

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

  1. 4,4,4,4,4,…4,4,4,4,4,\ldots.
  2. 2,4,6,8,10,…2, 4, 6, 8, 10, \ldots.
  3. 0,0,0,2,4,6,8,10,…0,0,0,2,4,6,8,10,\ldots.
  4. 1,5,25,125,…1, 5, 25, 125, \ldots.
  5. 1,−3,9,−27,81,…1, -3, 9, -27, 81, \ldots.
  6. 1,0,5,0,25,0,125,0,…1, 0, 5, 0, 25, 0, 125, 0, \ldots.
  7. 0,1,0,0,2,0,0,3,0,0,4,0,0,5,…0, 1, 0, 0, 2, 0, 0, 3, 0, 0, 4, 0, 0, 5, \ldots.
2.5

Exercise 2

Find the sequence generated by the following generating functions:

  1. 4x1−x\dfrac{4x}{1-x}.
  2. 11−4x\dfrac{1}{1-4x}.
  3. x1+x\dfrac{x}{1+x}.
  4. 3x(1+x)2\dfrac{3x}{(1+x)^2}.
  5. 1+x+x2(1−x)2\dfrac{1+x+x^2}{(1-x)^2} (Hint: multiplication).
2.5

Exercise 4

Use differencing to find the generating function for 4,5,7,10,14,19,25,…4, 5, 7, 10, 14, 19, 25, \ldots.

2.5

Exercise 5

Find a generating function for the sequence with recurrence relation an=3an−1−an−2a_n = 3a_{n-1} - a_{n-2} with initial terms a0=1a_0 = 1 and a1=5a_1 = 5.

2.5

Exercise 6

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

2.5

Exercise 7

Use multiplication to find the generating function for the sequence of partial sums of Fibonacci numbers, S0,S1,S2,…S_0, S_1, S_2, \ldots where S0=F0S_0 = F_0, S1=F0+F1S_1 = F_0 + F_1, S2=F0+F1+F2S_2 = F_0 + F_1 + F_2, S3=F0+F1+F2+F3S_3 = F_0 + F_1 + F_2 + F_3 and so on.

2.5

Exercise 8

Find the generating function for the sequence with closed formula an=2(5n)+7(−3)na_n = 2(5^n) + 7(-3)^n.

2.5

Exercise 9

Find a closed formula for the nnth term of the sequence with generating function 3x1−4x+11−x\dfrac{3x}{1-4x} + \dfrac{1}{1-x}.

2.5

Exercise 12

Starting with the generating function for 1,2,3,4,…1,2,3,4, \ldots, find a generating function for each of the following sequences.

  1. 1,0,2,0,3,0,4,…1, 0, 2, 0, 3, 0, 4,\ldots.
  2. 1,−2,3,−4,5,−6,…1, -2, 3, -4, 5, -6, \ldots.
  3. 0,3,6,9,12,15,18,…0, 3, 6, 9, 12, 15, 18, \ldots.
  4. 0,3,9,18,30,45,63,…0, 3, 9, 18, 30, 45, 63,\ldots. (Hint: relate this sequence to the previous one.)
2.5

Exercise 13

You may assume that 1,1,2,3,5,8,…1, 1, 2, 3, 5, 8,\ldots has generating function 11−x−x2\dfrac{1}{1-x-x^2} (because it does). Use this fact to find the sequence generated by each of the following generating functions.

  1. x21−x−x2\frac{x^2}{1-x-x^2}.
  2. 11−x2−x4\frac{1}{1-x^2-x^4}.
  3. 11−3x−9x2\frac{1}{1-3x-9x^2}.
  4. 1(1−x−x2)(1−x)\frac{1}{(1-x-x^2)(1-x)}.
2.5

Exercise 15

Find the generating function for the sequence 1,1,1,2,3,4,5,6,…1, 1, 1, 2, 3, 4, 5, 6, \ldots.

2.5

Adapted from Discrete Mathematics: An Open Introduction © 2013–2019 Oscar Levin. Licensed under CC BY-SA 4.0. Source: Discrete Mathematics: An Open Introduction. Imported at revision 1e2e26b.