Discrete Math Quiz: Generating Functions

17 questions · exam conditions

0:00

Generating FunctionsQuestion 1 of 17

The sequence $a_n$ satisfies the recurrence $a_n = 3a_{n-1} - 2a_{n-2}$ for $n \geq 2$ with $a_0 = 1$ and $a_1 = 4$ . If $G(x) = \sum_{n=0}^{\infty} a_n x^n$ is the generating function for this sequence, which equation must $G(x)$ satisfy?

G(x) = 1 + 4x + 3xG(x) - 2x^2G(x)

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

(1 - 3x + 2x^2)G(x) = 1 + x

G(x) = 1 + 4x + (3x - 2x^2)\sum_{n=2}^{\infty} a_n x^n

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Generating Functions

Practice Generating Functions in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Generating Functions, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

$G(x) = 1 + 4x + 3xG(x) - 2x^2G(x)$
$G(x) = \frac{1 + x}{1 - 3x + 2x^2}$
$(1 - 3x + 2x^2)G(x) = 1 + x$ (correct answer)
$G(x) = 1 + 4x + (3x - 2x^2)\sum_{n=2}^{\infty} a_n x^n$

Explanation: Starting with the recurrence relation

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

, multiply by

x^n

and sum from

n=2

\infty

\sum_{n=2}^{\infty} a_n x^n = 3\sum_{n=2}^{\infty} a_{n-1} x^n - 2\sum_{n=2}^{\infty} a_{n-2} x^n

. This gives

G(x) - a_0 - a_1 x = 3x(G(x) - a_0) - 2x^2 G(x)

. Substituting

a_0 = 1

and

a_1 = 4

G(x) - 1 - 4x = 3x(G(x) - 1) - 2x^2 G(x)

. Expanding:

G(x) - 1 - 4x = 3xG(x) - 3x - 2x^2 G(x)

. Rearranging:

G(x) - 3xG(x) + 2x^2 G(x) = 1 + 4x - 3x = 1 + x

. Therefore

(1 - 3x + 2x^2)G(x) = 1 + x

. Choice A incorrectly starts the generating function equation. Choice B gives the closed form but not the functional equation. Choice D uses an incorrect indexing approach.

Question 2

Two sequences $\{u_n\}$ and $\{v_n\}$ have generating functions related by $V(x) = \frac{d}{dx}[x \cdot U(x)]$ , where $U(x) = \frac{1}{1-2x}$ . What is the relationship between the sequences $\{u_n\}$ and $\{v_n\}$ ?

$v_n = (n+2) \cdot 2^{n-1}$ for $n \geq 0$ , calculated using the product rule and series manipulation
$v_n = n \cdot 2^{n-1}$ for $n \geq 1$ and $v_0 = 0$ , obtained through careful index management
$v_n = 2^n + n \cdot 2^{n-1}$ for $n \geq 1$ , combining the original and shifted derivative terms
$v_n = (n+1) \cdot 2^n$ for $n \geq 0$ , derived from the differentiation and multiplication rules (correct answer)

Explanation: When working with generating functions and derivatives, you need to carefully apply differentiation rules and track how they affect the corresponding sequences. Starting with

U(x) = \frac{1}{1-2x}

, you can recognize this as the generating function for

u_n = 2^n

. To find

V(x) = \frac{d}{dx}[x \cdot U(x)]

, first multiply:

x \cdot U(x) = \frac{x}{1-2x}

. Now differentiate using the quotient rule:

V(x) = \frac{d}{dx}\left[\frac{x}{1-2x}\right] = \frac{(1-2x)(1) - x(-2)}{(1-2x)^2} = \frac{1-2x+2x}{(1-2x)^2} = \frac{1}{(1-2x)^2}

The generating function

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

corresponds to the sequence

v_n = (n+1) \cdot 2^n

for

n \geq 0

. This follows from the general formula that

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

generates

(n+1)a^n

. Option A gives

v_n = (n+2) \cdot 2^{n-1}

, which would correspond to a different generating function with an extra factor. Option B incorrectly sets

v_0 = 0

and uses

2^{n-1}

instead of

2^n

, suggesting confusion about index shifts. Option C adds an extra

2^n

term that doesn't arise from the differentiation process. Study tip: When differentiating generating functions, remember that

\frac{d}{dx}[x \cdot f(x)]

often increases the power of coefficients by 1. Practice recognizing standard forms like

\frac{1}{(1-ax)^2} \leftrightarrow (n+1)a^n

Question 3

Consider the recurrence relation $a_n = a_{n-1} + a_{n-2} + 2^{n-2}$ for $n \geq 2$ with $a_0 = 0$ and $a_1 = 1$ . Which expression represents the generating function for the sequence $\{a_n\}$ ?

$\frac{x + \frac{x^2}{1-2x}}{1-x-x^2}$ , combining homogeneous and particular solution components
$\frac{x(1-2x) + x^2}{(1-x-x^2)(1-2x)}$ , using the method of undetermined coefficients systematically (correct answer)
$\frac{x + x^2}{1-x-x^2} + \frac{x^2}{1-2x}$ , treating homogeneous and non-homogeneous parts independently
$\frac{x(1-x) + 2x^2}{(1-x-x^2)(1-2x)}$ , derived through direct generating function manipulation techniques

Explanation: This is a non-homogeneous recurrence. Let

G(x) = \sum_{n=0}^{\infty} a_n x^n

. From the recurrence

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

for

n \geq 2

, multiply by

x^n

and sum:

\sum_{n=2}^{\infty} a_n x^n = \sum_{n=2}^{\infty} a_{n-1} x^n + \sum_{n=2}^{\infty} a_{n-2} x^n + \sum_{n=2}^{\infty} 2^{n-2} x^n

. This gives

G(x) - a_0 - a_1 x = x(G(x) - a_0) + x^2 G(x) + x^2 \sum_{n=0}^{\infty} 2^n x^n

. Substituting

a_0 = 0, a_1 = 1

G(x) - x = xG(x) + x^2 G(x) + \frac{x^2}{1-2x}

. Rearranging:

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

. Therefore

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

. Choice A has the right structure but incorrect numerator form. Choice C incorrectly separates the generating function additively. Choice D has wrong coefficients in the numerator.

Question 4

Consider the generating function $G(x) = \frac{x^2}{(1-x)^3}$ . If this generating function is shifted to start from the constant term (i.e., we define $\tilde{G}(x) = x^{-2}G(x)$ ), what recurrence relation does the resulting sequence satisfy?

$a_n = 3a_{n-1} - 3a_{n-2} + a_{n-3}$ with initial conditions determined by the shift operation (correct answer)
$a_n = a_{n-1} + 2a_{n-2}$ with modified boundary conditions reflecting the polynomial adjustment
$a_{n+2} = 3a_{n+1} - 3a_n + a_{n-1}$ with the index shift incorporated into the relation
$a_n = 3a_{n-1} - 2a_{n-2}$ with coefficients adjusted for the denominator factorization pattern

Explanation: Starting with

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

, when we define

\tilde{G}(x) = x^{-2}G(x) = \frac{1}{(1-x)^3}

, we get a generating function with denominator

(1-x)^3

. The generating function

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

corresponds to the sequence of triangular numbers (shifted): the coefficient of

x^n

\binom{n+2}{2}

. For a generating function of the form

\frac{P(x)}{(1-x)^k}

, the corresponding recurrence comes from the fact that

(1-x)^{-k}

satisfies

(1-x)^k \sum a_n x^n = \text{polynomial}

. For

k=3

, we have

(1-x)^3 = 1 - 3x + 3x^2 - x^3

, so the recurrence relation is

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

for

n \geq 3

, which rearranges to

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

. Choice B has the wrong number of terms and coefficients. Choice C incorrectly shifts the indices in the recurrence. Choice D uses incorrect coefficients that don't match the

(1-x)^3

expansion.

Question 5

The generating function $R(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^3}$ counts the number of ways to make change using coins of denominations 1 and 3. What is the coefficient of $x^7$ in this generating function?

$6$ , calculated through the convolution of individual denomination generating functions
$8$ , counting all possible ways including different orderings of the same coins
$5$ , obtained by systematic enumeration of valid coin combinations with repetition allowed
$3$ , representing the distinct combinations of coins that sum to 7 (correct answer)

Explanation: When you encounter generating functions for coin change problems, you're looking at a powerful tool that encodes the number of ways to make each amount using specific denominations. The generating function

R(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^3}

represents using unlimited coins of value 1 and 3, where the coefficient of

x^n

tells you how many ways you can make amount

n

. To find the coefficient of

x^7

, you need to determine how many non-negative integer solutions exist for

a + 3b = 7

, where

a

is the number of 1-cent coins and

b

is the number of 3-cent coins. Systematically checking values: when

b = 0

a = 7

(using seven 1's); when

b = 1

a = 4

(using four 1's and one 3); when

b = 2

a = 1

(using one 1 and two 3's). For

b \geq 3

, we'd need

3b \geq 9 > 7

, so no solutions exist. This gives us exactly 3 distinct combinations. Answer A incorrectly suggests 6 through convolution calculations, likely from computational error. Answer B's result of 8 suggests counting ordered arrangements rather than combinations—but generating functions count combinations, not permutations. Answer C's value of 5 represents systematic enumeration but with an incorrect count, possibly double-counting or including invalid combinations. Remember: in coin change generating functions, coefficients count distinct combinations of coins, not arrangements. Always convert to the equation

\sum d_i \cdot n_i = \text{target}

and solve systematically for non-negative integers.

Question 6

Consider the generating function $F(x) = \frac{2}{1-5x+6x^2}$ . If this represents the generating function for a sequence $\{b_n\}$ satisfying a homogeneous linear recurrence, what is the characteristic equation of that recurrence?

$r^2 - 5r + 6 = 0$ with initial conditions requiring specific determination (correct answer)
$r^2 + 5r - 6 = 0$ with roots determining the exponential growth pattern
$6r^2 - 5r + 1 = 0$ with coefficients derived from the denominator structure
$r^2 - 6r + 5 = 0$ with characteristic roots obtained by coefficient reversal

Explanation: For a generating function of the form

\frac{P(x)}{1 + c_1 x + c_2 x^2}

, the corresponding recurrence relation is

a_n + c_1 a_{n-1} + c_2 a_{n-2} = 0

for

n \geq 2

. Here we have

F(x) = \frac{2}{1 - 5x + 6x^2}

, so

c_1 = -5

and

c_2 = 6

. This gives the recurrence

a_n - 5a_{n-1} + 6a_{n-2} = 0

, or equivalently

a_n = 5a_{n-1} - 6a_{n-2}

. The characteristic equation is

r^2 - 5r + 6 = 0

. Choice B incorrectly flips signs. Choice C incorrectly reverses the coefficient order. Choice D swaps the middle and last coefficients.

Question 7

Consider the generating function $S(x) = \exp\left(\frac{x}{1-x}\right)$ . If $S(x) = \sum_{n=0}^{\infty} s_n x^n$ , what can be said about the growth rate of the coefficients $s_n$ as $n \to \infty$ ?

The coefficients grow exponentially, with $s_n \sim C \cdot r^n$ for some constants $C$ and $r > 1$
The coefficients grow polynomially, with $s_n = O(n^k)$ for some fixed positive integer $k$
The coefficients grow super-exponentially, faster than any exponential function but slower than factorial (correct answer)
The coefficients grow factorially, with $s_n \sim \frac{n!}{C^n}$ for some constant $C > 1$

Explanation: When analyzing the growth rate of coefficients in a generating function, you need to examine the singularities and behavior of the function to determine how quickly the coefficients grow. For

S(x) = \exp\left(\frac{x}{1-x}\right)

, the key insight is examining what happens near the dominant singularity at

x = 1

. As

x \to 1^-

, the expression

\frac{x}{1-x}

grows like

\frac{1}{1-x}

, which approaches infinity. This means

S(x)

has essential singularity behavior near

x = 1

, growing faster than any polynomial power of

\frac{1}{1-x}

. Using singularity analysis techniques, when a generating function has an essential singularity of the form

\exp\left(\frac{1}{1-x}\right)

near

x = 1

, the coefficients grow super-exponentially. Specifically, they grow faster than

r^n

for any fixed

r

, but slower than

n!

. This places the growth in the super-exponential category, making (C) correct. (A) is wrong because exponential growth

C \cdot r^n

occurs when you have simple pole singularities, not essential singularities. (B) is incorrect since polynomial growth

O(n^k)

corresponds to functions with algebraic singularities, not the exponential-type singularity we have here. (D) is wrong because factorial growth

\sim \frac{n!}{C^n}

would require a more severe singularity structure. Strategy tip: When you see generating functions with exponential expressions involving

\frac{1}{1-x}

, immediately think super-exponential growth. The essential singularity created by the exponential function is the telltale sign that coefficients will grow faster than any exponential but slower than factorial.

Question 8

A sequence $\{d_n\}$ satisfies $d_0 = 2$ , $d_1 = 1$ , and $d_n = 2d_{n-1} + 3d_{n-2}$ for $n \geq 2$ . If we define $f(x) = \sum_{n=0}^{\infty} d_n x^{n+1}$ , what is the closed form of $f(x)$ ?

$\frac{2x + x^2}{1 - 2x - 3x^2}$ , obtained by applying the standard generating function transformation
$\frac{x(2 - 3x)}{1 - 2x - 3x^2}$ , derived through careful manipulation of the shifted series (correct answer)
$\frac{2x + x^2}{1 + 2x + 3x^2}$ , found by incorporating the sign changes in the recurrence
$\frac{x(2 + x)}{1 - 2x - 3x^2}$ , calculated using the index shift and initial condition adjustments

Explanation: We have

f(x) = \sum_{n=0}^{\infty} d_n x^{n+1} = x \sum_{n=0}^{\infty} d_n x^n = x \cdot D(x)

, where

D(x)

is the standard generating function for

\{d_n\}

. From the recurrence

d_n = 2d_{n-1} + 3d_{n-2}

, we get

D(x) = \frac{d_0 + (d_1 - 2d_0)x}{1 - 2x - 3x^2} = \frac{2 + (1 - 4)x}{1 - 2x - 3x^2} = \frac{2 - 3x}{1 - 2x - 3x^2}

. Therefore,

f(x) = x \cdot D(x) = \frac{x(2 - 3x)}{1 - 2x - 3x^2}

. Choice A incorrectly computes the numerator after the shift. Choice C has the wrong sign in the denominator. Choice D has an incorrect numerator that doesn't account for the initial conditions properly.

Question 9

The generating functions $F(x) = \sum_{n=0}^{\infty} f_n x^n = \frac{2x}{1-x^2}$ and $G(x) = \sum_{n=0}^{\infty} g_n x^n = \frac{1}{1-x^2}$ are related to sequences with special properties. What is the relationship between the sequences $\{f_n\}$ and $\{g_n\}$ ?

$f_n = 2g_n$ for all even $n$ and $f_n = 0$ for all odd $n$
$f_n = 2g_n$ for all odd $n$ and $f_n = 0$ for all even $n$
$f_n = g_{n-1} + g_{n+1}$ for all $n \geq 1$
$f_n = 2g_{n-1}$ for all $n \geq 1$ and $f_0 = 0$ (correct answer)

Explanation: When you encounter generating functions, you're looking at a powerful tool that encodes sequence information in polynomial form. The key insight is that algebraic relationships between generating functions translate directly to relationships between their coefficient sequences. To find the relationship between

\{f_n\}

and

\{g_n\}

, let's first expand these generating functions. For

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

, we can use the geometric series formula:

G(x) = 1 + x^2 + x^4 + x^6 + \cdots

. This means

g_0 = g_2 = g_4 = \cdots = 1

and

g_1 = g_3 = g_5 = \cdots = 0

. For

F(x) = \frac{2x}{1-x^2} = 2x \cdot \frac{1}{1-x^2} = 2x \cdot G(x)

, we get

F(x) = 2x(1 + x^2 + x^4 + \cdots) = 2x + 2x^3 + 2x^5 + \cdots

. Therefore,

f_0 = 0

f_1 = 2

f_2 = 0

f_3 = 2

, and so on. Notice that

f_1 = 2 = 2g_0

f_3 = 2 = 2g_2

f_5 = 2 = 2g_4

. In general,

f_n = 2g_{n-1}

for

n \geq 1

, and

f_0 = 0

. This confirms answer D. Looking at the wrong answers: A incorrectly states the relationship holds for even

n

when it actually holds for odd

n

. B has the right parity but wrong formula - it's not

f_n = 2g_n

. C suggests a recurrence relation that doesn't match our coefficient analysis. Study tip: When comparing generating functions, multiply or factor them algebraically first, then extract coefficients systematically. The algebraic manipulation often reveals the sequence relationship immediately.

Question 10

Consider the recurrence relation $a_n = 3a_{n-1} - 2a_{n-2}$ for $n \geq 2$ with initial conditions $a_0 = 1$ and $a_1 = 4$ . If $G(x) = \sum_{n=0}^{\infty} a_n x^n$ is the generating function for this sequence, what is the correct form of $G(x)$ after applying the recurrence relation method?

$G(x) = \frac{1 + x}{1 - 3x + 2x^2}$ (correct answer)
$G(x) = \frac{1 - x}{1 + 3x - 2x^2}$
$G(x) = \frac{1 + x}{1 + 3x - 2x^2}$
$G(x) = \frac{1 - x}{1 - 3x + 2x^2}$

Explanation: Starting with G(x) = a₀ + a₁x + a₂x² + ..., we multiply the recurrence by xⁿ and sum. This gives G(x) - a₀ - a₁x = 3x(G(x) - a₀) - 2x²G(x). Substituting a₀ = 1 and a₁ = 4: G(x) - 1 - 4x = 3x(G(x) - 1) - 2x²G(x). Expanding: G(x) - 1 - 4x = 3xG(x) - 3x - 2x²G(x). Collecting terms: G(x)(1 - 3x + 2x²) = 1 + x. Therefore G(x) = (1 + x)/(1 - 3x + 2x²). Choice B has wrong signs in denominator, choice C has wrong sign on 3x term, choice D has wrong numerator.

Question 11

A sequence satisfies $a_n = a_{n-1} + a_{n-2}$ for $n \geq 2$ with $a_0 = 0$ and $a_1 = 1$ . If we want to find the coefficient of $x^5$ in the generating function $G(x)$ , which intermediate step correctly represents the algebraic manipulation needed?

$G(x) = x + x \cdot G(x) + x^2 \cdot G(x)$
$G(x) = x + G(x) \cdot x + G(x) \cdot x^2$
$(1 - x - x^2) \cdot G(x) = x$ (correct answer)
$(1 + x + x^2) \cdot G(x) = x$

Explanation: From the recurrence aₙ = aₙ₋₁ + aₙ₋₂, multiplying by xⁿ and summing gives ∑aₙxⁿ = ∑aₙ₋₁xⁿ + ∑aₙ₋₂xⁿ. This becomes G(x) - a₀ - a₁x = x(G(x) - a₀) + x²G(x). With a₀ = 0, a₁ = 1: G(x) - x = xG(x) + x²G(x). Rearranging: G(x) - xG(x) - x²G(x) = x, so (1 - x - x²)G(x) = x. Choice A incorrectly places x outside, choice B is the same error, choice D has wrong signs in the factor.

Question 12

A sequence $\{c_n\}$ has generating function $C(x) = \frac{1-x}{1-3x+2x^2}$ . If we factor the denominator as $(1-r_1 x)(1-r_2 x)$ where $r_1 > r_2 > 0$ , what can we conclude about the long-term behavior of $c_n$ as $n \to \infty$ ?

$c_n$ approaches a constant value as $n$ increases
$c_n$ alternates between positive and negative values indefinitely
$c_n$ grows like $r_1^n$ with the ratio $c_{n+1}/c_n$ approaching $r_1$ (correct answer)
$c_n$ decreases exponentially and approaches zero as $n$ increases

Explanation: When you encounter a generating function problem asking about long-term behavior, you need to analyze the poles (roots of the denominator) to understand how the sequence behaves asymptotically. First, let's factor the denominator

1-3x+2x^2

. Setting it equal to zero:

2x^2-3x+1=0

, which factors as

(2x-1)(x-1)=0

. So

x = \frac{1}{2}

and

x = 1

. This means the denominator factors as

(1-2x)(1-x) = (1-r_1x)(1-r_2x)

where

r_1 = 2

and

r_2 = 1

. Using partial fraction decomposition, we can write

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

for some constants

A

and

B

. Each term

\frac{1}{1-rx}

generates the sequence

r^n

, so

c_n = A \cdot 2^n + B \cdot 1^n = A \cdot 2^n + B

. Since

2^n

grows much faster than the constant

B

, the dominant term is

A \cdot 2^n

. Therefore,

c_n

grows like

2^n = r_1^n

, and

\frac{c_{n+1}}{c_n}

approaches

r_1 = 2

n \to \infty

. This confirms answer (C). (A) is wrong because

2^n

grows exponentially, not toward a constant. (B) is incorrect because both roots are positive, so no alternating behavior occurs. (D) is false because the sequence grows rather than decreases—the dominant root

r_1 = 2 > 1

causes exponential growth. Study tip: The largest root in the denominator always determines long-term behavior. If the largest root

r > 1

, expect exponential growth; if

r < 1

, expect decay to zero.

Question 13

The generating function $H(x) = \frac{1 + 2x}{(1-x)(1-3x)}$ can be expanded using partial fractions. If $H(x) = \frac{A}{1-x} + \frac{B}{1-3x}$ , what sequence property can be directly inferred about the coefficients $h_n$ in $H(x) = \sum_{n=0}^{\infty} h_n x^n$ ?

$h_n$ grows exponentially with ratio between consecutive terms approaching 3
$h_n = A \cdot 1^n + B \cdot 3^n$ for all $n \geq 0$
$h_n$ satisfies the recurrence $h_n = 4h_{n-1} - 3h_{n-2}$
$h_n = A + B \cdot 3^n$ for all $n \geq 0$ (correct answer)

Explanation: When you see a generating function with partial fractions, you're looking at a powerful tool that directly reveals the form of the sequence coefficients. Each term in the partial fraction decomposition corresponds to a specific pattern in the resulting sequence. First, let's find the values of A and B. Using partial fractions on

H(x) = \frac{1 + 2x}{(1-x)(1-3x)} = \frac{A}{1-x} + \frac{B}{1-3x}

, we get

1 + 2x = A(1-3x) + B(1-x)

. Setting

x = 1

gives

3 = -2A

, so

A = -\frac{3}{2}

. Setting

x = \frac{1}{3}

gives

\frac{5}{3} = \frac{2B}{3}

, so

B = \frac{5}{2}

. The key insight is that

\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n

and

\frac{1}{1-3x} = \sum_{n=0}^{\infty} 3^n x^n

. Therefore,

h_n = A \cdot 1^n + B \cdot 3^n = A + B \cdot 3^n

. Choice A incorrectly focuses on growth rates rather than the explicit formula. Choice B uses the correct general form but incorrectly includes the

1^n

term explicitly, when

1^n = 1

simplifies to just a constant. Choice C gives a recurrence relation, which while mathematically equivalent, isn't what we can "directly infer" from the partial fraction form—that requires additional work. Choice D correctly recognizes that the partial fraction decomposition immediately gives us

h_n = A + B \cdot 3^n

. Remember: partial fractions in generating functions directly translate to explicit formulas for sequence terms. Each fraction

\frac{C}{1-rx}

contributes

C \cdot r^n

to the coefficient formula.

Question 14

A sequence $\{b_n\}$ satisfies $b_n = 5b_{n-1} - 6b_{n-2}$ for $n \geq 2$ . If the generating function $B(x) = \sum_{n=0}^{\infty} b_n x^n$ has the form $\frac{P(x)}{1-5x+6x^2}$ , and we know that $b_2 = 7$ , $b_3 = 23$ , what must be the degree of polynomial $P(x)$ ?

$P(x)$ has degree 0 (constant polynomial)
$P(x)$ has degree 1 (linear polynomial) (correct answer)
$P(x)$ has degree 2 (quadratic polynomial)
$P(x)$ has degree 3 (cubic polynomial)

Explanation: For a second-order recurrence aₙ = caₙ₋₁ + daₙ₋₂, the generating function has the form G(x) = (a₀ + (a₁ - ca₀)x)/(1 - cx - dx²). Here c = 5, d = -6, so the denominator is 1 - 5x + 6x². The numerator P(x) = b₀ + (b₁ - 5b₀)x. Since we need exactly two initial conditions to determine a second-order recurrence completely, and we're given b₂ and b₃, we can work backwards to find b₀ and b₁. This gives P(x) as a linear polynomial (degree 1). Choice A would only work if b₁ = 5b₀, choice C would suggest a third-order recurrence, choice D is impossible for a second-order recurrence.

Question 15

Two sequences $\{u_n\}$ and $\{v_n\}$ have generating functions $U(x) = \frac{1}{1-2x}$ and $V(x) = \frac{x}{1-x-x^2}$ respectively. What is the coefficient of $x^4$ in the generating function for the sequence $\{w_n\}$ where $w_n = u_n + v_n$ ?

$16$
$19$ (correct answer)
$21$
$23$

Explanation: W(x) = U(x) + V(x) = 1/(1-2x) + x/(1-x-x²). From U(x) = ∑2ⁿxⁿ, we get u₄ = 2⁴ = 16. For V(x) = x/(1-x-x²), this generates the Fibonacci sequence shifted: v₀ = 0, v₁ = 1, v₂ = 1, v₃ = 2, v₄ = 3 (since V(x) = x·F(x) where F(x) is the standard Fibonacci generating function). Therefore w₄ = u₄ + v₄ = 16 + 3 = 19. Choice A gives only u₄, choice C and D represent common arithmetic errors in computing Fibonacci terms or powers of 2.

Question 16

Consider the generating function $G(x) = \frac{x^2}{1 - x - x^2 - x^3}$ . This function represents a sequence where each term depends on how many previous terms?

Each term depends on the previous 2 terms only
Each term depends on the previous 3 terms only (correct answer)
Each term depends on the previous 2 or 3 terms depending on the index
Each term depends on all previous terms in the sequence

Explanation: The denominator 1 - x - x² - x³ indicates a third-order recurrence relation. From G(x) = x²/(1 - x - x² - x³), we can derive that the sequence satisfies aₙ = aₙ₋₁ + aₙ₋₂ + aₙ₋₃ for n ≥ 3, after accounting for initial conditions determined by the numerator x². This is a third-order linear recurrence, meaning each term depends on exactly the previous 3 terms. Choice A would correspond to denominator 1 - ax - bx², choice C suggests a variable-order recurrence (which this is not), choice D would require an infinite sum in the denominator.

Question 17

The generating function $G(x) = \frac{2}{1 - 4x + 3x^2}$ corresponds to a sequence that satisfies a second-order linear recurrence. What are the characteristic roots of this recurrence relation?

$r_1 = 1, r_2 = 3$ (correct answer)
$r_1 = 3, r_2 = 1$
$r_1 = 4, r_2 = -3$
$r_1 = -1, r_2 = -3$

Explanation: The generating function G(x) = 2/(1 - 4x + 3x²) corresponds to the recurrence aₙ = 4aₙ₋₁ - 3aₙ₋₂. The characteristic equation is r² - 4r + 3 = 0, which factors as (r - 1)(r - 3) = 0, giving roots r₁ = 1 and r₂ = 3. Choice B gives the same roots in different order (which is equivalent), choice C incorrectly uses coefficients from the denominator directly, choice D has wrong signs.