Day 55 — Solving recurrences

Updated

July 30, 2026

Day 55 — Solving recurrences

Stage V · concept day
Goal: Solve first-order linear and second-order linear homogeneous recurrences with constant coefficients; use summation-factor idea; meet ordinary generating functions lite (Fibonacci GF sketch).

Why this matters

Closed forms turn “\(T(n)=2T(n/2)+n\)” into “\(\Theta(n\log n)\)” and “\(F_n\)” into Binet. Generating functions package infinite sequences into algebra—later probability and combinatorics use them heavily. Today: practical solution recipes + GF awareness, not full theory.

Theory

First-order linear homogeneous

\[ a_n = c\, a_{n-1},\qquad a_0=A \implies a_n = A\, c^n. \]

If \(a_1=A\) as base: \(a_n=A c^{n-1}\).

First-order linear nonhomogeneous (constant inhomogeneity)

\[ a_n = c\, a_{n-1} + d,\qquad c\neq 1. \]

Equilibrium / particular solution: constant \(a=c a+d\Rightarrow a=d/(1-c)\).
General: \(a_n = K c^n + \frac{d}{1-c}\).
Fit \(K\) from base case.

If \(c=1\): \(a_n=a_{n-1}+d\Rightarrow a_n=a_0+nd\).

Summation idea: unfold

\[ a_n=c a_{n-1}+d=c(c a_{n-2}+d)+d=\cdots=c^n a_0+d\sum_{j=0}^{n-1}c^j=c^n a_0+d\frac{c^n-1}{c-1}\ (c\neq 1). \]

Second-order linear homogeneous

\[ a_n = p\, a_{n-1} + q\, a_{n-2},\qquad n\ge 2. \]

Characteristic equation:

\[ r^2 - p r - q = 0. \]

Case 1: two distinct roots \(r_1,r_2\).

\[ a_n = A r_1^n + B r_2^n. \]

Solve \(A,B\) from \(a_0,a_1\).

Case 2: repeated root \(r\).

\[ a_n = (A+Bn)r^n. \]

Fibonacci closed form (Binet)

\(F_n=F_{n-1}+F_{n-2}\), \(F_0=0,F_1=1\).
Characteristic: \(r^2-r-1=0\), roots \(\phi=\frac{1+\sqrt{5}}{2}\), \(\hat\phi=\frac{1-\sqrt{5}}{2}\).
\(F_n=A\phi^n+B\hat\phi^n\); \(F_0=0\Rightarrow B=-A\); \(F_1=1\Rightarrow A(\phi-\hat\phi)=1\Rightarrow A=1/\sqrt{5}\).
Thus

\[ F_n = \frac{\phi^n-\hat\phi^n}{\sqrt{5}}. \]

Nearest integer to \(\phi^n/\sqrt{5}\) for \(n\ge 1\).

Hanoi closed form

\(H_n=2H_{n-1}+1\), \(H_0=0\): from first-order recipe, \(H_n=2^n-1\).

Divide-and-conquer (unfolding lite)

\(T(n)=2T(n/2)+n\), \(n=2^k\), \(T(1)=\Theta(1)\):

\[ T(n)=n+2\cdot\frac{n}{2}+4\cdot\frac{n}{4}+\cdots+n\cdot T(1)=n\log_2 n+O(n). \]

Master theorem (Stage VIII) generalizes.

Ordinary generating functions (lite)

The ordinary generating function (OGF) of \((a_n)_{n\ge 0}\) is

\[ A(x)=\sum_{n=0}^{\infty} a_n x^n. \]

Algebra of OGFs (awareness):

  • \(A+B\) ↔︎ termwise sum;
  • \(xA(x)\) ↔︎ shift right (roughly);
  • \(1/(1-x)=\sum x^n\);
  • \(1/(1-cx)=\sum c^n x^n\).

Fibonacci GF derivation sketch

Let \(F(x)=\sum_{n\ge 0} F_n x^n\) with \(F_0=0,F_1=1\).
From \(F_n=F_{n-1}+F_{n-2}\) (\(n\ge 2\)):

\[ F(x)-F_0-F_1 x = x(F(x)-F_0)+x^2 F(x). \]

So \(F(x)-x = x F(x)+x^2 F(x)\), hence

\[ F(x)=\frac{x}{1-x-x^2}. \]

Extract coefficients: partial fractions using roots of \(1-x-x^2=0\), recover Binet—sketch only.

Simple coefficient extraction

  • \(\sum\binom{n}{k}x^k=(1+x)^n\) finite.
  • \([x^n]\frac{1}{(1-x)^{k+1}}=\binom{n+k}{k}\) (negative binomial / stars-and-bars link).

Worked examples

Example 1 — Geometric

\(a_n=5a_{n-1}\), \(a_0=2\) → \(a_n=2\cdot 5^n\).

Example 2 — Affine

\(a_n=3a_{n-1}+2\), \(a_0=1\).
Particular: \(a=3a+2\Rightarrow a=-1\).
General: \(a_n=K\cdot 3^n-1\). \(a_0=1\Rightarrow K-1=1\Rightarrow K=2\).
\(a_n=2\cdot 3^n-1\). Check: \(a_1=5\), \(3\cdot 1+2=5\).

Example 3 — Summation unfold

\(a_n=2a_{n-1}+1\), \(a_0=0\): \(a_n=\sum_{j=0}^{n-1}2^j=2^n-1\).

Example 4 — Characteristic distinct

\(a_n=5a_{n-1}-6a_{n-2}\), \(a_0=0,a_1=1\).
\(r^2-5r+6=0=(r-2)(r-3)\).
\(a_n=A\cdot 2^n+B\cdot 3^n\).
\(A+B=0\), \(2A+3B=1\Rightarrow A=-1,B=1\).
\(a_n=3^n-2^n\).

Example 5 — Fibonacci check

\(F_5=\frac{\phi^5-\hat\phi^5}{\sqrt{5}}=5\).

Example 6 — Repeated root

\(a_n=4a_{n-1}-4a_{n-2}\), \(a_0=1,a_1=4\).
\((r-2)^2=0\). \(a_n=(A+Bn)2^n\).
\(A=1\); \(a_1=(A+B)2=4\Rightarrow A+B=2\Rightarrow B=1\).
\(a_n=(1+n)2^n\).

Example 7 — Hanoi

Already \(2^n-1\).

Example 8 — Merge sort

\(T(32)=32\cdot 5=160\) if \(T(n)=n\log_2 n\) with zero base cost idealized.

Example 9 — GF geometric

\(a_n=3^n\): \(A(x)=1/(1-3x)\) for \(|3x|<1\) formally.

Example 10 — Stars-bars GF

Number of nonnegative solutions \(x_1+\cdots+x_k=n\) is \([x^n](1-x)^{-k}=\binom{n+k-1}{k-1}\).

Example 11 — Fit constants carefully

\(a_n=a_{n-1}+2a_{n-2}\), \(a_0=3,a_1=1\).
\(r^2-r-2=0=(r-2)(r+1)\).
\(a_n=A 2^n+B(-1)^n\).
\(A+B=3\), \(2A-B=1\Rightarrow A=\frac{4}{3},B=\frac{5}{3}\). Wait: \(A+B=3\), \(2A-B=1\) add: \(3A=4\), \(A=4/3\), \(B=5/3\). Check \(a_2=a_1+2a_0=1+6=7\); formula \((4/3)4+(5/3)=16/3+5/3=7\).

Example 12 — Nonhomogeneous polynomial (awareness)

\(a_n=2a_{n-1}+n\): particular of form \(An+B\); solve and add homogeneous \(K\cdot 2^n\). (Optional practice.)

Example 13 — Partial fractions lite

\(F(x)=x/(1-x-x^2)\) factors as \(c_1/(1-\phi x)+c_2/(1-\hat\phi x)\)—leads to Binet.

Example 14 — Verify by induction

Prove \(a_n=2\cdot 3^n-1\) satisfies Ex. 2 by induction after guessing.

Example 15 — Catalan GF awareness

\(C(x)=\sum C_n x^n\) satisfies \(C=1+x C^2\)—quadratic, not linear recurrence method.

Exercises

  1. Solve \(a_n=7a_{n-1}\), \(a_0=3\).
  2. Solve \(a_n=2a_{n-1}+5\), \(a_0=1\).
  3. Solve \(a_n=a_{n-1}+4\), \(a_0=2\).
  4. Characteristic roots for \(a_n=a_{n-1}+6a_{n-2}\).
  5. Solve \(a_n=5a_{n-1}-6a_{n-2}\), \(a_0=0,a_1=1\) (Ex. 4 style—already).
  6. Solve \(a_n=6a_{n-1}-9a_{n-2}\), \(a_0=1,a_1=3\).
  7. Binet: compute \(F_6\) via formula (should be 8).
  8. Prove by induction \(H_n=2^n-1\).
  9. Unfold \(T(n)=2T(n/2)+n\) for \(n=2^k\) to closed form.
  10. Write OGF for \(a_n=1\) all \(n\); for \(a_n=n\).
  11. Show \([x^n](1-x)^{-3}=\binom{n+2}{2}\).
  12. Derive \(F(x)=x/(1-x-x^2)\) carefully from scratch.
  13. Solve \(a_n=4a_{n-1}\), \(a_2=5\) (careful with index).
  14. \(a_n=3a_{n-1}+2^n\)—try particular \(K\cdot 2^n\) (note if 2 is root of homogeneous).
  15. Fib: solve with \(F_0=0,F_1=1\) for \(A,B\) again.
  16. Sequence \(1,2,4,8,\ldots\) recurrence + closed.
  17. \(a_n=2a_{n-1}-a_{n-2}\), \(a_0=5,a_1=5\)—what sequence?
  18. CS: closed form for number of subsets \(2^n\) from recurrence \(a_n=2a_{n-1}\).
  19. Master-ish: \(T(n)=3T(n/3)+n\), unfold sketch.
  20. GF: extract \([x^4]\) of \(1/(1-x-x^2)\) (related to Fib).
  21. Repeated root example of your own with numbers.
  22. Why characteristic method fails for \(a_n=n a_{n-1}\).
  23. Challenge: full particular solution for \(a_n=2a_{n-1}+n\).
  24. Limit \(F_{n+1}/F_n\to\phi\).
  25. Write a 5-step recipe card for order-2 homogeneous solving.

CS connection

  • Runtime closed forms from recurrences.
  • Amortized analysis cousin: unfolding sums.
  • Digital signal / linear filters: same linear recurrences.
  • Generating functions in combinatorics on words and probability pgfs (later).
  • Compiler loop strength reduction culture: closed forms of induction variables.

Common pitfalls

Pitfall What to do instead
Wrong characteristic polynomial sign \(r^2-pr-q=0\) for \(a_n=pa_{n-1}+qa_{n-2}\)
Forgetting to solve for \(A,B\) Use both bases
Repeated root missing \(n\) factor \((A+Bn)r^n\)
\(c=1\) case of \(a_n=ca_{n-1}+d\) Arithmetic sequence
GF as values not formal series Coefficient extraction mindset
Applying to nonlinear Catalan Different methods

Checkpoint

  • Solve order-1 affine cold
  • Characteristic equation method for order 2
  • Binet formula statement
  • Unfold one divide-and-conquer
  • Fib GF \(x/(1-x-x^2)\)
  • Exercises 1–15
  • Recipe card written

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. \(a_n=3\cdot 7^n\).
  2. Particular \(-5\); \(a_n=K\cdot 2^n-5\); \(K=6\); \(a_n=6\cdot 2^n-5\).
  3. \(a_n=2+4n\).
  4. \(r^2-r-6=0\), \(r=3,-2\).
  5. \((r-3)^2\); \(a_n=(1+0\cdot n)3^n=3^n\) if \(a_1=3\)—check \(a_1=(A+B)3=3\Rightarrow A+B=1\), \(A=1,B=0\).
  6. \(1/(1-x)\); \(x/(1-x)^2\).
  7. Constant 5 (double root 1: \(a_n=A+Bn\), \(B=0\)).
  8. \([x^4]F(x)/x\) related—\([x^4]1/(1-x-x^2)=F_5=5\) if \(1/(1-x-x^2)=\sum F_{n+1}x^n\).

Deepening notes

Recipe card — order 2 homogeneous

  1. Write \(a_n - p a_{n-1} - q a_{n-2}=0\).
  2. Characteristic \(r^2-pr-q=0\).
  3. Distinct roots: \(A r_1^n+B r_2^n\); repeated: \((A+Bn)r^n\).
  4. Solve \(A,B\) from \(a_0,a_1\).
  5. Verify \(a_2\) by both recurrence and closed form.

Unfolding template order 1

\(a_n=c a_{n-1}+d = c^n a_0 + d\sum_{j=0}^{n-1}c^j\).
Geometric sum closed form depending on \(c=1\) or not.

GF coefficient dictionary

OGF \([x^n]\)
\(1/(1-x)\) \(1\)
\(1/(1-cx)\) \(c^n\)
\(x/(1-x)^2\) \(n\)
\(1/(1-x)^{k+1}\) \(\binom{n+k}{k}\)
\(x/(1-x-x^2)\) \(F_n\)

Extra drills

D1. \(a_n=4a_{n-1}+3\), \(a_0=0\).
D2. \(a_n=a_{n-1}+6a_{n-2}\), \(a_0=3,a_1=1\).
D3. Binet \(F_7=13\) check.
D4. Prove \(H_n=2^n-1\) by induction.
D5. Unfold \(T(n)=2T(n/2)+3n\).
D6. GF for \(a_n=2^n\).
D7. Repeated root: \(a_n=2a_{n-1}-a_{n-2}\), \(a_0=1,a_1=3\).
D8. Partial fractions sketch for Fib GF.

Flash

\(r^2-pr-q=0\); \(F_n=(\phi^n-\hat\phi^n)/\sqrt5\); \(F(x)=x/(1-x-x^2)\).

Tomorrow

Day 56 — Story proofs: combinatorial vs algebraic; double counting; bijections; hockey-stick.