Solving linear recurrence relations

A recurrence relation defines each term of a sequence from earlier ones, and many counting problems produce one naturally. Moving a tower of \( n \) discs in the Tower of Hanoi means moving \( n - 1 \) discs aside, the largest disc across, and \( n - 1 \) discs back on top: \( h_n = 2h_{n-1} + 1 \) with \( h_1 = 1 \). Binary strings of length \( n \) with no two consecutive 1s either end in 0 (after any good string of length \( n-1 \)) or in 01 (after any good string of length \( n-2 \)): \( s_n = s_{n-1} + s_{n-2} \). Solving a recurrence means finding a closed formula for the \( n \)-th term.

A linear homogeneous recurrence with constant coefficients of order 2 has the form \( a_n = c_1 a_{n-1} + c_2 a_{n-2} \). Try \( a_n = r^n \): dividing by \( r^{n-2} \) gives the characteristic equation \( r^2 = c_1 r + c_2 \). If it has two distinct roots \( r_1, r_2 \), every solution is \[ a_n = A\,r_1^n + B\,r_2^n, \] with \( A \) and \( B \) fixed by the two initial values. For \( a_n = 5a_{n-1} - 6a_{n-2} \) the example solves \( r^2 - 5r + 6 = 0 \) to get \( r = 2, 3 \); with \( a_0 = 2 \) and \( a_1 = 5 \), the equations \( A + B = 2 \) and \( 2A + 3B = 5 \) give \( A = B = 1 \), so \( a_n = 2^n + 3^n \).

If the characteristic equation has a repeated root \( r \), the second solution is \( n r^n \), and the general solution is \( a_n = (A + Bn)\,r^n \). The same idea extends to order \( k \): each root of multiplicity \( m \) contributes \( r^n, nr^n, \dots, n^{m-1}r^n \). The Fibonacci recurrence has roots \( (1 \pm \sqrt 5)/2 \), which gives Binet's formula \( F_n = (\varphi^n - \psi^n)/\sqrt 5 \).

A non-homogeneous recurrence \( a_n = c_1 a_{n-1} + c_2 a_{n-2} + g(n) \) is solved as general homogeneous solution plus one particular solution, guessed in the shape of \( g \): a constant for a constant, a polynomial of the same degree for a polynomial, \( C\,s^n \) for \( s^n \). If \( s \) is a characteristic root of multiplicity \( m \), multiply the guess by \( n^m \) (for a constant or polynomial term, \( s = 1 \)). For Hanoi, try the constant \( h_n = C \): \( C = 2C + 1 \) gives \( C = -1 \), so \( h_n = A\,2^n - 1 \), and \( h_1 = 1 \) gives \( h_n = 2^n - 1 \).

Picture it: plot the terms on a log scale. The solution \( A r_1^n + B r_2^n \) quickly becomes a straight line whose slope is the logarithm of the largest root: the dominant root decides the growth rate, and the others fade into a correction.

Think it: this is the discrete twin of solving \( y'' - 5y' + 6y = 0 \) with \( e^{rx} \), and the reasons are the same: the solutions form a vector space whose dimension is the order, and the characteristic roots give a basis. Always check the formula against the first few terms computed directly from the recurrence.