Day 54 — Recurrences intro

Updated

July 30, 2026

Day 54 — Recurrences intro

Stage V · concept day
Goal: Define sequences by recurrence; identify linear homogeneous relations; set up Fibonacci, Tower of Hanoi, tiling, and divide-and-conquer recurrences; enforce base-case discipline.

Why this matters

Algorithms that call themselves, structures that grow by local rules, and counting problems with “last step” cases produce recurrences. Before solving (Day 55), you must set them up correctly: domain, order, base cases, and what $a_n$ means. A wrong base case poisons every later term.

Theory

What is a recurrence?

A recurrence relation defines each term of a sequence using previous terms. Example:

\[ a_n = 2a_{n-1} + 1,\qquad a_0=0. \]

The relation + base case(s) determine the sequence uniquely (when well-posed).

Explicit vs recursive definition

Closed form / explicit: $a_n=2^n-1$ (formula in $n$ only).
Recursive: defined from earlier values.
Day 55 converts many linear recurrences to closed forms.

Order and homogeneity

Order $k$: $a_n$ depends on $a_{n-1},\ldots,a_{n-k}$ (needs $k$ bases).
Linear: $a_n$ is a linear combination of previous terms plus optional $f(n)$.
Homogeneous: $f(n)=0$ (no extra forcing term).
Constant coefficients: coefficients do not depend on $n$.

Example: $a_n=a_{n-1}+a_{n-2}$ — linear homogeneous order 2, constant coeffs (Fibonacci-like).
Example: $a_n=3a_{n-1}+2^n$ — linear nonhomogeneous.
Example: $a_n=n a_{n-1}$ — linear, variable coefficient.

Domain of the recurrence

State for which $n$ the relation holds (often $n\ge 2$ or $n\ge 1$).
Base cases cover the smallest $n$ outside that range.
Never apply the recurrence below its domain.

Fibonacci sequence

Standard indexing variants exist—fix yours:

\[ F_0=0,\; F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\ (n\ge 2). \]

So $0,1,1,2,3,5,8,13,21,34,\ldots$.

Counting story: number of ways to tile a $1\times n$ board with tiles of size 1 and 2: $T_n=T_{n-1}+T_{n-2}$, $T_0=1$, $T_1=1$, so $T_n=F_{n+1}$.

Bit-strings length $n$ with no two consecutive 1s: $a_n=a_{n-1}+a_{n-2}$ (end with 0: $a_{n-1}$ ways; end with 01… wait end with 0: $a_{n-1}$; end with 1: must …01, $a_{n-2}$). Bases: $a_1=2$ (0,1), $a_2=3(00,01,10`).

Tower of Hanoi

Move $n$ disks from peg A to C, spare B; never larger on smaller.

\[ H_n = 2H_{n-1} + 1,\qquad H_0=0\ (H_1=1). \]

Story: move $n-1$ to spare ($H_{n-1}$), move largest to target ($1$), move $n-1$ onto target ($H_{n-1}$).
Closed form preview: $H_n=2^n-1$.

Merge-sort style recurrence

Sorting $n$ elements by split, recurse, merge:

\[ T(n)=2T(n/2)+cn,\qquad T(1)=\Theta(1), \]

for $n$ a power of 2 (setup; solving Day 55 / Master theorem Stage VIII).
Meaning: two half-size subproblems + linear merge work.

Binary search: $T(n)=T(n/2)+\Theta(1)$.

Last-step counting pattern

To count structures of size $n$:

Classify by a feature of the “end” or a distinguished piece.
Express counts in terms of smaller sizes.
Fix bases by enumeration.

Uniqueness / well-posedness

Given order-$k$ linear recurrence with fixed coefficients and $k$ consecutive initial values, there is a unique infinite sequence satisfying them.

Generating values by hand

Table method: write $n$ | $a_n$ and fill using the relation. Check bases twice.

Worked examples

Example 1 — Fibonacci table

$F_0..F_{10}$: 0,1,1,2,3,5,8,13,21,34,55.

Example 2 — Tiling

$T_n$ tilings of $n$-board with 1s and 2s: $T_0=1,T_1=1,T_2=2,T_3=3,T_4=5,T_5=8$.

Example 3 — Hanoi

$H_1=1,H_2=3,H_3=7,H_4=15=2^4-1$.

Example 4 — Bit-strings no consecutive 1s

$a_1=2,a_2=3,a_3=a_2+a_1=5,a_4=8,a_5=13$.

Example 5 — Set up only

Number of ways to climb $n$ stairs taking 1 or 2 steps: same as tiling $T_n$.

Example 6 — Nonhomogeneous

$a_n=2a_{n-1}+1$, $a_0=0$: compute $0,1,3,7,15$ → guess $2^n-1$.

Example 7 — Factorial recurrence

$n!=n\cdot(n-1)!$, $0!=1$—variable coefficient, solution is factorial.

Example 8 — Regions (optional classic)

Maximum regions by $n$ lines in general position: $R_n=R_{n-1}+n$, $R_0=1$.
($R_n=1+n(n+1)/2$.)

Example 9 — Merge sort expand

$T(n)=2T(n/2)+n$, $T(1)=0$:
$T(n)=n+2T(n/2)=n+2(n/2+2T(n/4))=\cdots=n\log_2 n$ for $n=2^k$.

Example 10 — Wrong bases

If $F_0=1,F_1=1$ then you get $1,1,2,3,5,\ldots$ (often called Fibonacci too—indexing shift). State clearly.

Example 11 — Strings over ternary

Length $n$ over $\{0,1,2\}$ no two consecutive equal: $a_n=3\cdot 2^{n-1}$ closed; recurrence $a_n=2a_{n-1}$, $a_1=3$.

Example 12 — Derangement recurrence

$!n=(n-1)[!(n-1)+!(n-2)]$ with $!0=1,!1=0$—order 2, non-constant-looking but standard.

Example 13 — Catalan recurrence

$C_0=1$, $C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}$—nonlinear (quadratic). Not linear constant coeff.

Example 14 — Domain care

$a_n=a_{n-1}+2a_{n-2}$ for $n\ge 2$ needs $a_0,a_1$. If someone gives only $a_1$, sequence not determined.

Example 15 — CS call tree

$C(n)=C(n-1)+C(n-2)+1$ counting nodes in Fib recursion tree—different from Fib values themselves.

Exercises

Compute $F_{12}$ from bases.
Tiling $T_8$ with singles and dominoes.
Hanoi $H_6$ and verify $2^6-1$.
Bit-strings length 6 no consecutive 1s.
Set up recurrence for ways to write $n$ as ordered sum of 1s and 2s (compositions).
$a_n=3a_{n-1}$, $a_0=5$: list to $a_5$; guess closed form.
$a_n=a_{n-1}+n$, $a_0=0$: compute to $a_6$; closed form?
Why does order 2 need two bases? Counterexample with one base.
Merge sort: expand $T(16)$ with $T(n)=2T(n/2)+n$, $T(1)=0$.
Binary search $T(n)=T(\lfloor n/2\rfloor)+1$, $T(1)=1$: value at $n=16$.
Climb stairs 1, 2, or 3 at a time: recurrence + bases; $a_5$.
Strings length $n$ over $\{0,1\}$ ending with 0 vs 1—system of recurrences optional.
Regions $R_n=R_{n-1}+n$, $R_0=1$: closed form.
Explain why Catalan recurrence is not linear.
Set up $a_n$ for perfect binary tree height $n$ node count.
CS: number of calls to compute Fib($n$) naively—recurrence.
$a_n=na_{n-1}$, $a_0=1$: what is $a_n$?
Write bases wrong on purpose for Hanoi and show damage at $n=4$.
Multistep: define $a_n=2^n$ both closed and as recurrence.
No two consecutive equal letters from 26-letter alphabet length $n$.
Longest path counting? (skip)—instead: number of subsets of $[n]$ via recurrence $a_n=2a_{n-1}$.
Domain: for $a_n=a_{n/2}+1$ ($n$ even), what bases and domain issues?
Challenge: recurrence for derangements $!n=n\cdot!(n-1)+(-1)^n$.
Table: compute 10 terms of $a_n=2a_{n-1}-a_{n-2}$, $a_0=1,a_1=3$.
Story: number of binary strings length $n$ with no 011—set up states (harder) or skip to: no 00 only.

CS connection

Runtime recurrences: divide-and-conquer algorithms.
Dynamic programming: DP is organized recurrence evaluation.
Data structure sizes: tree node counts, path lengths.
Combinatorial generation: recursive structure of objects (trees, tilings).
Loop invariants cousin: recurrences describe discrete time evolution of state counts.

Common pitfalls

Pitfall	What to do instead
Missing or wrong bases	Enumerate small $n$ carefully
Off-by-one in “size $n$” meaning	Define $a_n$ in words first
Applying recurrence for $n$ too small	State domain $n\ge n_0$
Indexing Fibonacci inconsistently	Fix $F_0,F_1$ in writing
Confusing $T(n)$ time with $a_n$ counts	Separate notations
Nonlinear treated as linear	Catalan ≠ characteristic eq method

Checkpoint

Define order, linear, homogeneous
Fib, tiling, Hanoi setups with bases
Merge-sort recurrence meaning
Build a table of 8+ terms for a custom recurrence
Exercises 1–15
Explain base-case discipline in one sentence

Two personal takeaways:

Selected mini-solutions

$F_{12}=144$.
$T_8=F_9=34$.
$H_6=63$.
$a_6=21$ if $a_1=2,a_2=3$ Fib-like.
$a_n=5\cdot 3^n$.
$a_n=n(n+1)/2$.
$T(16)=16\cdot 4=64$ if $T(n)=n\log_2 n$ with $T(1)=0$.
$T(16)=5$ (five halvings to 1? $16\to8\to4\to2\to1$: 4 steps + base—define carefully: often $1+\log_2 n$).
$a_n=a_{n-1}+a_{n-2}+a_{n-3}$, $a_0=1,a_1=1,a_2=2$, $a_5=13$.
$a_n=n!$.

Deepening notes

Base-case audit procedure

Write $a_n$ in English (“number of … of size $n$”).
Compute $a_0$ or $a_1$ by listing.
Verify the recurrence at the smallest $n$ in its domain by listing both sides.
Only then compute further terms.

Fibonacci indexing wars

Some authors set $F_1=F_2=1$. Then their $F_n$ is your $F_n$ shifted. Always restate bases when quoting formulas (Binet is index-sensitive).

From recurrence to algorithm cost

$T(n)=2T(n/2)+n$ is merge sort; $T(n)=T(n-1)+n$ is insertion-sort style; $T(n)=T(n-1)+T(n-2)+O(1)$ is naive Fib time (exponential). The recurrence is the model of the algorithm’s call structure.

Extra drills

D1. Table $F_0..F_{15}$.
D2. $T_n$ tilings through $n=10$.
D3. Stairs 1 or 2 steps: $a_{10}$.
D4. $H_8=2^8-1$.
D5. No consecutive 1s strings length 8.
D6. $a_n=a_{n-1}+2a_{n-2}$, $a_0=1,a_1=1$ ten terms.
D7. Wrong base $H_0=1$—how $H_3$ breaks vs $2^n-1$.
D8. Set up recurrence for binary strings with no 000.

Flash

Order $k$ needs $k$ bases; Fib $F_n=F_{n-1}+F_{n-2}$; Hanoi $H_n=2H_{n-1}+1$; Merge $T(n)=2T(n/2)+n$.

Exam drill block

E1. Define order, linear, homogeneous, constant coefficients—with examples.
E2. Fib table to $F_{15}$; tiling $T_{10}$.
E3. Hanoi recurrence + closed form guess; verify $n=5$.
E4. No consecutive 1s: bases + $a_7$.
E5. Stairs 1/2/3: bases + $a_6$.
E6. Merge-sort expand $T(32)$.
E7. $a_n=3a_{n-1}+1$, $a_0=0$—compute 6 terms; guess form.
E8. Why Catalan recurrence is nonlinear.
E9. Domain error: apply $a_n=a_{n-1}+a_{n-2}$ at $n=1$ wrongly—show mess.
E10. CS: naive recursive Fib call count recurrence.

Mini solutions

E3. $H_5=31$.
E4. $a_7=34$ if $a_1=2,a_2=3$.
E6. $32\cdot 5=160$ idealized $n\log_2 n$.

Worked setup gallery

W1 — Tilings. $T_n=$ ways to tile $n$-board with $1$s and $2$s: $T_n=T_{n-1}+T_{n-2}$, $T_0=1,T_1=1$. Same as Fib shifted.

W2 — Hanoi. $H_n=2H_{n-1}+1$, $H_0=0$ or $H_1=1$ → closed $2^n-1$.

W3 — Merge sort cost. $T(n)=2T(n/2)+n$ for $n=2^k$, $T(1)=0$ → $T(n)=n\log_2 n$.

W4 — No consecutive 1s. $a_n=a_{n-1}+a_{n-2}$ (end in 0: $a_{n-1}$; end in 01… wait end in 1 ⇒ prev 0): standard Fib-like with $a_1=2,a_2=3$.

W5 — Stairs 1/2/3. $a_n=a_{n-1}+a_{n-2}+a_{n-3}$ with three base cases by listing.

Synthesis

A recurrence is a definition by smaller instances. Get order, linearity, and bases right before computing. Fibonacci family covers tilings and bit-strings; Hanoi and divide-and-conquer show algorithm costs. Listing small $n$ is the base-case audit. Closed forms wait for Day 55.

S1. Set up and tabulate no-11 bit-strings through length 8.
S2. Write Hanoi recurrence, prove $H_n=2^n-1$ by induction.
S3. Cold: $F_{10}$, $T_8$ tilings, $H_7$.

Checklist before solving (Day 55)

Domain of $n$ stated
Exactly $k$ bases for order $k$
Recurrence verified at smallest legal $n$
Homogeneous vs inhomogeneous noted
Algorithm cost vs combinatorial count distinguished

Tomorrow

Day 55 — Solving recurrences: characteristic equation, first-order linear, generating functions lite.