Solving Recurrences Analytically

Hard4 hrsCharacteristic EquationHomogeneous RecurrenceParticular SolutionClosed Form

Overview

Once you've set up a recurrence using first-step analysis, you often need the closed-form solution. The standard technique is characteristic equations for linear recurrences. For the gambler's ruin (second-order), the characteristic equation gives two roots r₁ and r₂, and the general solution is A·r₁ⁿ + B·r₂ⁿ with boundary conditions pinning A and B. For non-homogeneous recurrences (with a constant term), add a particular solution. In interviews, you usually don't need the full machinery — just know that the gambler's ruin with p=½ gives linear solution, p≠½ gives geometric solution.

How to Recognize

→You've set up a recurrence and need the closed form
→Linear recurrences of the form aₙ = α·aₙ₋₁ + β·aₙ₋₂ + ... + c
→Probability problems requiring a non-iterative answer
→Interviewers ask 'can you simplify that?'

Step-by-Step Approach

1.For linear homogeneous: guess aₙ = rⁿ, solve characteristic equation for r
2.General solution: aₙ = A·r₁ⁿ + B·r₂ⁿ (two roots); apply boundary conditions
3.For non-homogeneous: find particular solution + homogeneous solution
4.First-order linear: aₙ = p·aₙ₋₁ + c solves to aₙ = c/(1-p) + (a₀ - c/(1-p))·pⁿ
5.Generating functions: useful when recurrences have complex structure

Key Formulas

a_n = \alpha a_{n-1} + \beta a_{n-2}

: characteristic roots

r^2 = \alpha r + \beta

a_n^* = c/(1-p)

— particular solution to

a_n = p\,a_{n-1} + c

(p≠1)

\text{Fibonacci: } F_n = (\phi^n - \psi^n)/\sqrt{5}

where

\phi=(1+\sqrt5)/2

\text{Random walk: } E[T_x \to x\pm N] = N^2

(via } a_n = N^2 - (n-\text{start})^2)$

Worked Examples

0Quick Example

Pₙ = ½Pₙ₋₁ + ½Pₙ₊₁, with P₀=0, P_N=1. Characteristic eq: 2r² = r + 1... wait, rewrite: Pₙ₊₁ - 2Pₙ + Pₙ₋₁ = 0. Roots: r=1 (double). General: Pₙ = A + Bn. Boundary: P₀=0 → A=0; P_N=1 → B=1/N. So Pₙ = n/N.

Problem

Derive the closed-form formula for P(reaching N | start at k) in the biased gambler's ruin where P(+1)=p, P(-1)=q=1-p, p≠½.

Solution

Recurrence: pₖ = p·pₖ₊₁ + q·pₖ₋₁, i.e., p·pₖ₊₁ - pₖ + q·pₖ₋₁ = 0.

Divide by p: pₖ₊₁ - (1/p)·pₖ + (q/p)·pₖ₋₁ = 0.

Characteristic equation: r² - (1/p)r + (q/p) = 0, i.e., pr² - r + q = 0.

Roots: r = [1 ± √(1-4pq)]/(2p). Note 1-4pq = (p-q)². Roots: r₁=1, r₂=q/p.

General solution: pₖ = A·1ᵏ + B·(q/p)ᵏ = A + B·(q/p)ᵏ.

Boundary: p₀=0 → A+B=0 → B=-A. p_N=1 → A+B(q/p)^N=1 → A(1-(q/p)^N)=1 → A=1/(1-(q/p)^N).

Result: pₖ = [1 - (q/p)^k] / [1 - (q/p)^N].

Answer

$p_k = \frac{1-(q/p)^k}{1-(q/p)^N}$ . Fair case: $q/p \to 1$ , apply L'Hôpital → $p_k = k/N$ .

Common Mistakes

!
For fair case (p=½): trying to use the biased formula. When q/p=1, the formula gives 0/0. Take the limit or solve separately with the double-root case.
!
Applying boundary conditions wrong. Remember p₀ = 0 (not p₁) and p_N = 1.
!
For non-homogeneous recurrences: forgetting the particular solution. E.g., Eₖ = 1 + ½Eₖ₋₁ + ½Eₖ₊₁ has particular solution -k² (for the random walk case).

Practice Problems

Click "Show Answer" to reveal

Verify that the expected duration of gambler's ruin for a fair game, starting at k, targeting N, is k(N-k). Use the recurrence Tₖ = 1 + ½Tₖ₋₁ + ½Tₖ₊₁.

Hint: Try particular solution Tₖ = -k². The homogeneous solution is Aₖ + B. Apply T₀=0, T_N=0.

Back to Study Plan

Recursive Game Values Threshold Strategies