Derive a recurrence from a model
Build the recurrence before calculating. Define what a term counts, split configurations into exhaustive disjoint cases, and justify each term of the recurrence.
Concepts for §5.6
Before you begin
Sequences
A sequence assigns one value to each permitted index. Whether it starts at 0 or 1 is part of its definition.
a_n = 2n + 1, n ≥ 0
In a sum, the index takes every integer value from the lower bound through the upper bound.
∑_{i=0}^{2} a_i = a_0 + a_1 + a_2Definitions and notation for this topic
Recurrence relation
A rule expressing terms in terms of preceding terms.
The initial value and the range where the rule applies belong to the definition. This recurrence is an example, not a universal symbol for recurrence relations.
Separate glossary example
a₁=3 and a_n=a_(n−1)+2 for integers n≥2 define 3,5,7,9,… .
a₁=2; aₙ=aₙ₋₁+2 for n≥2.
Recursive and explicit sequence formulas
A recursive rule defines later terms using earlier ones and initial values. An explicit formula gives a_n directly in terms of n and fixed parameters.
Check an explicit candidate against both the recurrence and the initial values. Matching a few terms alone does not prove the formulas agree for every index.
Separate glossary example
a₀=3, a_n=a_(n−1)+2 for n≥1 describes the same sequence as a_n=3+2n for n≥0.
Worked example
Let a_n count length-n words over {0,1,2} with no two adjacent 2s. The empty word is permitted when n=0. Derive a recurrence with sufficient initial values, and use it to find a_4.
Your task
A strip of n consecutive squares is tiled without gaps or overlaps. A tile covering one square may be white or black; a grey tile covers exactly two consecutive squares. Tiles of the same type are indistinguishable, but the order of tiles and their colours matter. Let b_n count the tilings, including one empty tiling for n=0. Derive a recurrence and the required initial values. Explain why your cases are disjoint and exhaustive, then calculate b_5.
Saved in this browser; not automatically graded.
Review your written reasoning
- I defined what b_n counts and which indices are allowed.
- I counted the empty tiling and the two length-one tilings correctly.
- I justified the coefficient 2 and explained why the grey case has coefficient 1.
- I described both removal and reattachment, so the recurrence counts every tiling exactly once.
- My calculation begins at n=2 and gives 70, but the written derivation is also part of my answer.