A 2×n board can be tiled with 1×2 dominoes. Let T(n) be the number of tilings. Which recurrence and initial conditions are correct?
AT(n) = T(n-1) + T(n-2), with T(0) = 0 and T(1) = 1
BT(n) = T(n-1) + T(n-2), with T(0) = 1 and T(1) = 1
CT(n) = 2·T(n-1), with T(1) = 1
DT(n) = T(n-1) + T(n-2), with T(1) = 2 and T(2) = 3
Place the first domino: either vertically (covering column 1, leaving a 2×(n-1) board) or as two horizontals stacked (covering columns 1-2, leaving a 2×(n-2) board). So T(n) = T(n-1) + T(n-2). The base cases are T(0) = 1 (one way to tile an empty board — the empty tiling) and T(1) = 1 (only a vertical domino fits). Wrong initial conditions produce the wrong sequence, which is the most common setup error.
Question 2 True / False
A recurrence relation alone, without any initial conditions, uniquely determines a sequence.
TTrue
FFalse
Answer: False
A recurrence like aₙ = aₙ₋₁ + aₙ₋₂ is satisfied by infinitely many sequences depending on the starting values. For example, Fibonacci (0, 1, 1, 2, 3, ...) and Lucas (2, 1, 3, 4, 7, ...) both satisfy the same recurrence but have different initial conditions. Initial conditions are required to pin down a unique sequence.
Question 3 Short Answer
What does it mean to 'verify a recurrence against small cases,' and why is this step important?
Think about your answer, then reveal below.
Model answer: Compute the first several terms both by directly counting the objects (e.g., by hand or by enumeration) and by applying the recurrence formula, then confirm the two match.
Even a logically derived recurrence can have subtle errors — especially in the initial conditions or off-by-one boundary cases. Checking that T(1), T(2), T(3) match direct counts is a fast sanity check that catches most setup mistakes before you invest effort in solving the recurrence.