Recurrences and Difference Equations

Half the expected-value classics end at a system of equations like $E_k = 1 + \tfrac12 E_{k-1} + \tfrac12 E_{k+1}$. This lesson is the general theory of such equations, so instead of solving each puzzle from scratch you recognize the pattern and write the answer.

Homogeneous linear recurrences

For $a_n = c_1 a_{n-1} + c_2 a_{n-2}$, guess $a_n = r^n$. Substituting gives the characteristic equation $r^2 = c_1 r + c_2$; with roots $r_1 \ne r_2$ the general solution is

$$a_n = A r_1^n + B r_2^n,$$

with $A, B$ pinned by boundary conditions. Repeated root $r$: use $A r^n + Bn r^n$.

The showcase: Fibonacci, $r^2 = r + 1$, roots $\varphi = \frac{1+\sqrt5}{2}$ and $\hat\varphi = \frac{1-\sqrt5}{2}$, giving Binet's formula $F_n = \frac{\varphi^n - \hat\varphi^n}{\sqrt 5}$. Practical corollary: $F_n \approx \varphi^n/\sqrt5$ — growth rate questions ("roughly how big is $F_{30}$?") need only the dominant root. That principle — the largest root controls the asymptotics — is the entire long-run theory of linear systems in one sentence.

Ruin problems: the two-root machine

Biased gambler's ruin: win \$1 with probability$p$, lose with$q = 1-p$. The hitting probability$h_k$satisfies$h_k = p,h_{k+1} + q,h_{k-1}$. Characteristic equation$p r^2 - r + q = 0$has roots$1$and$q/p$, so

$$h_k = A + B\left(\frac{q}{p}\right)^k,$$

and boundaries $h_0 = 0$, $h_N = 1$ give the standard formula $h_k = \frac{1 - (q/p)^k}{1 - (q/p)^N}$. The fair case $p = q$ has a double root at 1, so $h_k = A + Bk$ — linear, which is exactly the "$k/N$" answer from the ruin question. What looked like two separate tricks is one method with different root structures.

Inhomogeneous equations: expected times

Expected-duration equations carry a "+1" forcing term: $T_k = 1 + p\,T_{k+1} + q\,T_{k-1}$. Recipe: general solution = homogeneous solution + any particular solution. For a constant forcing term, try a particular solution $T_k = ck$ (or $ck^2$ when the homogeneous part already contains linear terms — the fair case, which is how $T_k = k(N-k)$ arises). This "guess the right polynomial" step is mechanical once named, and it converts every expected-hitting-time interview question into four lines.

First-step analysis, formalized

The pattern-waiting problems (flips until HH, dice until two sixes) generate small systems rather than one recurrence: one unknown per state, one linear equation per state, solve. Two practical habits: order the unknowns so substitution cascades (solve the closest-to-done state first), and sanity-check monotonicity — being closer to the target must not increase the expected time. If it does, an equation is wrong, and finding it beats resolving everything.

The interview version

"A frog climbs stairs, hopping +1 with probability 2/3 and slipping −1 with probability 1/3. Expected hops from stair 0 to stair 10?" — Drift is $+1/3$ per hop, so the crude answer is $10 / (1/3) = 30$; the recurrence machinery confirms the linear particular solution $T_k = 3(10-k)$ satisfies boundary and equation, so exactly 30 (edge behavior at 0 permitting). Recognizing when drift alone answers the question — and when boundaries force the full two-root treatment — is the judgment this topic builds.