Self-Assessment Quiz: Recurrence Relations

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Question 1

A recurrence relation for a sequence $\{a_n\}$ is:

A) a formula that computes $a_n$ directly from $n$ B) an equation expressing $a_n$ in terms of one or more earlier terms C) the list of a sequence's first few values D) a proof that the sequence converges

Question 2

How many initial conditions does the recurrence $a_n = a_{n-1} + a_{n-3}$ require to determine a unique sequence?

A) 1 B) 2 C) 3 D) 4

Question 3

Which of these is a linear homogeneous recurrence with constant coefficients?

A) $a_n = a_{n-1}\,a_{n-2}$ B) $a_n = n\,a_{n-1}$ C) $a_n = 3a_{n-1} - 2a_{n-2}$ D) $a_n = 2a_{n-1} + 5$

Question 4

The characteristic equation of $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ is:

A) $r^2 - c_1 r - c_2 = 0$ B) $r^2 + c_1 r + c_2 = 0$ C) $c_1 r^2 + c_2 r + 1 = 0$ D) $r^2 - c_1 r + c_2 = 0$

Question 5

A second-order linear homogeneous recurrence has characteristic roots $r_1 = 5$ and $r_2 = -2$ (distinct). Its general solution is:

A) $a_n = (\alpha + \beta n)\,5^n$ B) $a_n = \alpha\, 5^n + \beta\,(-2)^n$ C) $a_n = \alpha\, 5^n \cdot \beta\,(-2)^n$ D) $a_n = \alpha\, 5^n - 2^n$

Question 6

A recurrence has characteristic equation $(r-4)^2 = 0$. The correct form of its general solution is:

A) $a_n = \alpha\, 4^n + \beta\, 4^n$ B) $a_n = \alpha\, 4^n$ C) $a_n = (\alpha + \beta n)\, 4^n$ D) $a_n = \alpha\, 4^n + \beta\,(-4)^n$

Question 7

The Tower of Hanoi recurrence $H_n = 2H_{n-1} + 1$ is not homogeneous because:

A) its coefficient is 2, not 1 B) it is only first-order C) of the standalone "$+1$" term, which carries no $a_{n-i}$ D) the roots are complex

Question 8

"Solving a recurrence" most precisely means:

A) computing one specific term by unrolling B) converting the recurrence into a closed form valid for all $n$ C) listing the first ten terms D) checking that the initial conditions are consistent

Question 9 (True/False, justify)

True or false: A linear homogeneous recurrence always produces a sequence that grows at most linearly in $n$. Justify in one sentence.

Question 10

For a nonhomogeneous recurrence $a_n = (\text{linear part}) + f(n)$, the general solution has the form $a_n = a_n^{(h)} + a_n^{(p)}$, where $a_n^{(h)}$ is:

A) any particular solution of the full recurrence B) the general solution of the associated homogeneous recurrence (drop $f(n)$) C) the forcing term $f(n)$ D) always a constant

Question 10b

To solve $a_n = 4a_{n-1} + 7$ (forcing term the constant 7, and 4 is not a root issue here), a good first guess for a particular solution is:

A) $a_n^{(p)} = A n$ B) $a_n^{(p)} = A$ (a constant) C) $a_n^{(p)} = A\,4^n$ D) $a_n^{(p)} = A\,7^n$

Question 11

For the recursive code shape "one call on input $n-1$, with $O(1)$ work in the current call," the time recurrence and growth are:

A) $T(n) = T(n/2) + c$, so $O(\log n)$ B) $T(n) = T(n-1) + c$, so $O(n)$ C) $T(n) = 2T(n-1) + c$, so exponential D) $T(n) = T(n-1) + cn$, so $O(n^2)$

Question 12

Naive recursive Fibonacci is unusably slow because the recurrence for its running time, $T(n) = T(n-1) + T(n-2) + c$:

A) has no closed form B) grows like $F_n$ itself, which is exponential C) is nonlinear D) requires three initial conditions

Question 13 (True/False, justify)

True or false: The recurrence $a_n = 2a_{n-1}$ alone (no initial condition) determines a unique sequence. Justify in one sentence.

Question 14

The $2 \times n$ domino-tiling count satisfies $t_n = t_{n-1} + t_{n-2}$. The setup move that produced the "$+t_{n-2}$" term was:

A) placing one vertical domino in the first column B) placing two horizontal dominoes that fill the first two columns C) the Tower of Hanoi reduction D) conditioning on the last symbol of a string

Question 15

Which recurrence is outside the reach of the characteristic-equation method of §18.4?

A) $a_n = a_{n-1} + a_{n-2}$ B) $a_n = 3a_{n-1} - 2a_{n-3}$ C) $a_n = a_{n-1}\,a_{n-2}$ D) $a_n = 4a_{n-1} - 4a_{n-2}$

Question 16 (Short answer)

State the two universal "setup moves" from §18.2 for building a recurrence from a problem, in a phrase each.

Question 17

When a trial particular solution for a nonhomogeneous recurrence is already a solution of the associated homogeneous recurrence, the fix is to:

A) give up; no closed form exists B) multiply the trial by $n$ (then $n^2$, …) until it is no longer a homogeneous solution C) add a constant D) switch to ordinary induction

Question 18 (Short answer)

The recurrence $a_n = a_{n-1} + a_{n-2}$ with $a_0 = 0, a_1 = 1$ gives Fibonacci. The same recurrence with $a_0 = 2, a_1 = 1$ gives a different sequence. What does this illustrate about recurrences and initial conditions, in one sentence?

Question 19

The discriminant of the characteristic equation $r^2 - r - 1 = 0$ (Fibonacci) is $5 > 0$. This tells you the roots are:

A) a single repeated real root B) two distinct real roots C) two complex conjugate roots D) undefined

Question 20 (Short answer)

In one sentence, explain why being able to read a recurrence directly off recursive code (§18.6) lets you predict an algorithm's growth rate before running it.

Answer Key

Topics to review by question