Questions: Recurrence Relations and Their Definitions

Question 1

The recurrence T(n) = 2T(n−1) with T(1) = 3 gives the sequence 3, 6, 12, 24, .... What sequence does T(n) = 2T(n−1) with T(1) = 1 produce?

• A. 3, 6, 12, 24, ... — the recurrence determines the sequence, not the initial value.
• B. 1, 2, 4, 8, ... — a different initial condition produces a different sequence.
• C. 0, 1, 2, 4, ... — the sequence shifts by one position when T(1) changes.
• D. 1, 3, 6, 12, ... — the new first term is prepended before the original sequence.

Answer: (B)

The same recurrence with different initial conditions produces entirely different sequences. With T(1) = 1, the terms are T(2) = 2, T(3) = 4, T(4) = 8, giving 1, 2, 4, 8, .... Option A reflects the core misconception that the recurrence alone determines the sequence — but without initial conditions, infinitely many sequences satisfy T(n) = 2T(n−1).

Question 2

A person climbs a staircase by taking 1 or 2 steps at a time. Let f(n) be the number of distinct ways to climb n stairs. Which recurrence captures this correctly?

• A. f(n) = 2 × f(n−1), because at every step there are always two choices.
• B. f(n) = f(n−1) × f(n−2), because the two sub-problems multiply together.
• C. f(n) = f(n−1) + f(n−2), because the last move was either 1 step (from position n−1) or 2 steps (from position n−2).
• D. f(n) = n × f(n−1), because more stairs means proportionally more paths.

Answer: (C)

Condition on the last move: if the final step was a single step, you arrived from stair n−1, with f(n−1) ways to have reached it; if it was a double step, you arrived from stair n−2, with f(n−2) ways. These cases are mutually exclusive and exhaustive, so f(n) = f(n−1) + f(n−2) — the Fibonacci recurrence. Option A is wrong because doubling the paths from n−1 ignores the distinct paths that arrive via a 2-step jump from n−2.

Question 3

The same recurrence relation with different initial conditions can produce entirely different sequences.

• T. True
• F. False

Answer: True

True. The recurrence gives the rule for continuation, but the initial conditions are what anchor the sequence. Fibonacci with F(1) = 1, F(2) = 1 gives 1, 1, 2, 3, 5, 8, ...; the same recurrence with F(1) = 2, F(2) = 2 gives 2, 2, 4, 6, 10, 16, .... Different starting points, same rule, different sequences.

Question 4

A recurrence relation alone is sufficient to uniquely determine a sequence.

• T. True
• F. False

Answer: False

False. A recurrence constrains how terms relate to each other but leaves the starting values unspecified. Without initial conditions, infinitely many sequences satisfy any given recurrence. For example, T(n) = T(n−1) + 1 is satisfied by 1, 2, 3, 4, ... and also by 5, 6, 7, 8, ... and by every arithmetic sequence with common difference 1. Initial conditions are what make the sequence unique.

Question 5

Why are initial conditions an essential component of a recurrence relation definition, and what goes wrong if they are omitted?

Model answer: Initial conditions specify the explicit values of the first one or more terms. Without them, the recurrence only tells you how each term relates to previous ones but provides no concrete anchor. As a result, infinitely many sequences satisfy the same recurrence. For example, any sequence aₙ = c · 2ⁿ satisfies aₙ = 2aₙ₋₁ for any constant c. Only by fixing a starting value — say a₁ = 3 — do we pin down a unique sequence.

A recurrence is like a rule for generating next steps without telling you where to start. Initial conditions are the foundation — the recurrence stacks terms on top of them. This parallels a differential equation needing initial values to select one unique solution from a family of solutions.