REASONING PRACTICE

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.

\displaystyle a_n = 2n + 1

\displaystyle n \ge 0

In a sum, the index takes every integer value from the lower bound through the upper bound.

\displaystyle \sum _{i=0}^{2} a_i = a_{0} + a_{1} + a_{2}

More in lesson §5.1 Summation Finite product

Definitions 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_{1}=3$ and $a_n=a_{n-1}+2$ for integers $n\ge 2$ define 3,5,7,9,… .

$a_{1}=2$ ; $a_{n}=a_{n-1}+2$ for $n\ge 2$ .

Open glossary card

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_{0}=3$ , $a_n=a_{n-1}+2$ for $n\ge 1$ describes the same sequence as $a_n=3+2n$ for $n\ge 0$ .

Open glossary card

Open the lesson §5.6

Colour cues

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}$ .

Your written attempt

Saved in this browser; not automatically graded.

Symbols

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.