Recurrence Relations Explained

What a recurrence relation actually is

A recurrence relation defines each term of a sequence in terms of one or more earlier terms. On its own it is incomplete: the rule a(n) = 2a(n-1) + 1 is satisfied by infinitely many different sequences, one for every starting value you pick. To specify a single sequence you must also give initial conditions, enough of them to get the rule started. A rule that reaches back k terms needs k initial conditions.

The order of a recurrence is how far back it reaches. The Towers of Hanoi rule a(n) = 2a(n-1) + 1 with a(0) = 0 is first order, since it looks back one step. The Fibonacci rule F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1 is second order, and needs two initial conditions because knowing only F(0) would leave the second term undetermined. A recurrence is linear when the earlier terms appear only to the first power and are never multiplied by each other, and homogeneous when every term involves the sequence, with no stray extra function of n.

• A recurrence plus its initial conditions determine exactly one sequence.
• Order is how far back the rule reaches; you need that many initial conditions.
• Linear: earlier terms appear to the first power and are not multiplied together.
• Homogeneous: no extra term depending on n alone, such as the +1 in the Hanoi rule.

Unrolling: the honest way to guess

Unrolling, also called iteration or back-substitution, means applying the rule to itself repeatedly and watching for a pattern. Take a(n) = 2a(n-1) + 1 with a(0) = 0. Substituting gives a(n) = 2(2a(n-2) + 1) + 1, which is 4a(n-2) + 2 + 1, and once more 8a(n-3) + 4 + 2 + 1. The shape is now clear: after k steps you have 2^k times a(n-k), plus the sum of the powers of 2 below 2^k.

Push all the way down to a(0), which is 0, and what survives is 1 + 2 + 4 + ... + 2^(n-1), a geometric sum equal to 2^n - 1. Check it against the sequence the recurrence generates directly, which starts 0, 1, 3, 7, 15, 31: the formula gives exactly those terms. That check matters, because unrolling produces a conjecture, not a proof. The rigorous finish is induction.

The characteristic equation

For a linear homogeneous recurrence with constant coefficients there is a method that beats guessing. Consider the second-order case a(n) = c1 a(n-1) + c2 a(n-2). Try a solution of the pure exponential form a(n) = r^n for some nonzero r. Substituting gives r^n = c1 r^(n-1) + c2 r^(n-2), and dividing through by r^(n-2) leaves r^2 = c1 r + c2, a plain quadratic. Rearranged as r^2 - c1 r - c2 = 0, this is the characteristic equation, and its roots are the only exponential bases that can work.

The Fibonacci recurrence F(n) = F(n-1) + F(n-2) therefore has characteristic equation x^2 = x + 1, whose roots are the golden ratio (1 + sqrt 5)/2, about 1.618, and (1 - sqrt 5)/2, about -0.618. Because the recurrence is linear, any combination of solutions is again a solution, so the general solution is A r1^n + B r2^n whenever the two roots are distinct. The constants A and B are then fixed by the initial conditions, and only at that step does one particular sequence emerge from the family.

• Substitute r^n into the recurrence and divide out the lowest power of r.
• Distinct roots r1 and r2 give the general solution A r1^n + B r2^n.
• A repeated root r gives (A + Bn) r^n, since r^n alone is not enough.
• Solve for A and B by plugging in the initial conditions.

A worked example with distinct roots

Solve a(n) = 5a(n-1) - 6a(n-2) with a(0) = 1 and a(1) = 4. The characteristic equation is r^2 - 5r + 6 = 0, which factors as (r - 2)(r - 3) = 0, so the roots are 2 and 3 and the general solution is A times 2^n plus B times 3^n. The initial conditions give two equations: at n = 0, A + B = 1, and at n = 1, 2A + 3B = 4.

Substituting A = 1 - B into the second equation gives 2 - 2B + 3B = 4, so B = 2 and A = -1. The closed form is a(n) = 2 times 3^n minus 2^n. Verify it against the recurrence rather than trusting the algebra: the rule generates 1, 4, 14, 46, 146, 454, and the formula gives 2 - 1 = 1, 6 - 2 = 4, 18 - 4 = 14, 54 - 8 = 46, and so on. They agree, which is the sanity check to run every time.

When the root repeats

If the characteristic equation has a double root the two-exponential recipe collapses, because r1^n and r2^n become the same function and cannot be combined to meet two independent initial conditions. The fix is to take r^n and n times r^n as the two basic solutions, giving the general form (A + Bn) r^n. The extra factor of n is what restores the missing degree of freedom.

Take a(n) = 6a(n-1) - 9a(n-2) with a(0) = 1 and a(1) = 9. The characteristic equation r^2 - 6r + 9 = 0 factors as (r - 3)^2, a double root at 3, so a(n) = (A + Bn) 3^n. At n = 0 this gives A = 1, and at n = 1 it gives (1 + B) times 3 = 9, so B = 2 and the closed form is (1 + 2n) 3^n. Checked against the recurrence, both produce 1, 9, 45, 189, 729, 2673.

Reading a recurrence for growth

Often you need only the growth rate, and the characteristic roots hand that to you. The largest root in absolute value dominates as n grows, so the sequence grows like that root to the n. Fibonacci grows like the golden ratio to the n because the second root is smaller than 1 in absolute value and its contribution shrinks away, which is why consecutive Fibonacci numbers approach a ratio of about 1.618.

This is also where recurrences meet algorithm analysis. A recursive procedure making two calls on inputs one smaller has a running time obeying T(n) = 2T(n-1) + constant, and the root of 2 says immediately that the cost doubles with each increment. Recognising the shape of the recurrence is often the whole of the analysis.

• The root with the largest absolute value sets the growth rate.
• Roots smaller than 1 in absolute value fade as n grows.
• A root above 1 means exponential growth; a root of exactly 1 contributes a constant.
• Growth rate is often enough for algorithm analysis, without solving for A and B.