Using characteristic equation to solve general linear recurrence relations

A general linear recurrence relation is a recurrence relation with the form shown below:

\displaystyle c_0a_n+c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}=f(n)

We have already seen many famous recurrence relations in the past, such as Fibonacci numbers and Lucas numbers. Here are some of the examples of linear recurrence relations:

  1. {a_n=a_{n-1}+a_{n-2}}
  2. {a_n-a_{n-1}=3\dbinom{n+2}{3}}

The first equation above is also known as a homogeneous linear recurrence relation, since it does not contain the {f(n)} term. There are many ways which can be employed to solve such recurrence relations. You can use generating functions, characteristic equation, or simply guess and check using mathematical induction. Don’t underestimate the last approach, it comes in very handy for complicated recurrence relations.

Anyway, my most preferred method of solving such recurrence relations is to use characteristic equation. Students who have learned differential equations should be familiar with characteristic equations. Basically we convert the recurrence relation into a polynomial equation and solve for its roots. Next, we use its roots and some specific form of recurrence relation to find out the general term. The approach is slightly different for homogeneous and non-homogeneous linear recurrences. In the case of a homogeneous linear recurrence relation, it assumes the following general form:

\displaystyle c_0a_n+c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}=0

The characteristic equation will be in the form:

\displaystyle c_0x^k+c_1x^{k-1}+c_2x^{k-2}+\cdots c_{k-1}x+c_k=0

By solving the characteristic equation, we can obtain {k} solutions {x_1, x_2, \cdots, x_k} (not necessarily real and distinct). Now we suppose all these solutions are distinct. The general solution to the recurrence relation will be in the form:

\displaystyle a_n=A_1x_1^n+A_2x_2^n+\cdots A_kx_k^n

where {A_1, A_2, \cdots A_k} are coefficients to be determined. These coefficients can be determined by substituting {k} different values of {a_n} (usually given in the question) and solving the simultaneous equations.

On the other hand, if there are repeated roots in the solution set, simply replace the coefficient of the corresponding repeated root by {(B_1+B_2n+B_3n^2+\cdots+B_ln^{l-1})} where {l} is the number of times that the root is repeated.

In the example below, we shall attempt to find out the general term for Fibonacci sequence:

Let {(a_n)} be a sequence which satisfies the conditions {a_0=1, a_1=1, a_n=a_{n-1}+a_{n-2}}. Derive the general term for the sequence {(a_n)}.

The above recurrence relation is a linear recurrence relation of second order (meaning {a_n} is dependent on two preceding values {a_{n-1}} and {a_{n-2}}). The characteristic equation of the sequence is {x^2=x+1}. Solving the equation, we obtain the solutions

\displaystyle x_1=\dfrac{1+\sqrt{5}}{2} \qquad x_2=\dfrac{1-\sqrt{5}}{2}

Hence, the general term of the solution is in the form

\displaystyle a_n=A\left(\dfrac{1+\sqrt{5}}{2}\right)^n+B\left(\dfrac{1-\sqrt{5}}{2}\right)^n

Plugging the values for {n=0, 1}, we obtain the following system of simultaneous equations:

\begin{cases}A+B=1\\ \left(\dfrac{1+\sqrt{5}}{2}\right)A+\left(\dfrac{1-\sqrt{5}}{2}\right)B=1 \end{cases}

This gives us the values of {A} and {B}, which are

\displaystyle A=\dfrac{1+\sqrt{5}}{2\sqrt{5}} \qquad B=-\dfrac{1-\sqrt{5}}{2\sqrt{5}}

Upon simplification, we obtain the general formula for Fibonacci sequence (also known as Binet’s formula)

\displaystyle a_n=\dfrac{1}{\sqrt{5}} \left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right]

The approach in solving a general linear recurrence relation is less obvious and involves more computation. As such, it rarely comes out in MO. The general solution will be in the form of {a_n=a_{n_1}+a_{n_2}}, where {a_{n_1}} is the solution of the corresponding homogeneous linear recurrence while {a_{n_2}} is a function which is similar to the form of {f(n)}. I will use the following example to illustrate the technique:

Solve the recurrence relation {a_n-2a_{n-1}=3-n^2} given {a_0=1}

The corresponding linear homogeneous recurrence relation of the above equation is {a_n-2a_{n-1}=0}. It’s general solution is {a_n=A2^n} for some constant {A} to be determined later. As such, {a_{n_1}=A2^n}. Right now, we need to determine {a_{n_2}} which should be in the form of {Bn^2+Cn+D} since {f(n)} is a quadratic function.

Now, {a_{n_2}} is supposed to satisfy the recurrence relation. As such, we have:

\displaystyle (Bn^2+Cn+D)-2[B(n-1)^2+C(n-1)+D]=3-n^2

By rearranging and comparing coefficients, we obtain the following system of equations:

\displaystyle \begin{cases} B-2B=-1\\ C+4B-2C=0\\ D-2B+2C-2D=3 \end{cases}

Solving the above system, we obtain {B=1, C=4} and {D=3}. This makes it clear that {a_{n_2}=n^2+4n+3} and hence {a_n=A2^n+n^2+4n+3}. By plugging the value of {a_0}, we finally obtain {A=-2}. Hence the final answer is {-2^{n+1}+n^2+4n+3}.

Not all recurrence relations can be solved like this. Coincidentally, we are able to set {a_{n_2}=Bn^2+Cn+D} because the characteristic root is not 1 and the function is a polynomial function. If that’s not the case, further modification has to be made to the function that we choose. It is much simpler to solve this class of problems using generating functions or method of telescoping sum (for first order recurrence relations).

Here are some practice problems for the topic:

  1. (USAMO 1973 P2) Let {(X_n)} and {(Y_n)} denote two sequences of integers defined as follows:

    \displaystyle X_0=1, X_1=1, X_{n+1}=X_n+2X_{n-1} \\ Y_0=1, Y_1=7, Y_{n+1}=2Y_n+3Y_{n-1}

    Prove that, except for the ’1′, there is no term which occurs in both sequences

  2. (SMO(O)1999 P8) For each positive integer {n}, let {a_n} denote the number of {n}-digit integers formed by some or all of the digits 1, 2, 3, 4 and 5 in such a way that 1 is not followed by 1 and 2 is not followed by 2 in each of these integers. Find {a_n} in terms of {n}.
  3. (IMO 1979 P6) Let {A} and {E} be opposite vertices of an octagon. A frog starts at vertex {A}. From any vertex except {E} it jumps to one of the two adjacent vertices. When it reaches {E} it stops. Let {a_n} be the number of distinct paths of exactly {n} jumps ending at {E}. Prove that

    \displaystyle a_{2n-1}=0, \qquad a_{2n}=\dfrac{(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}}{\sqrt{2}}.


About these ads

One thought on “Using characteristic equation to solve general linear recurrence relations

  1. Pingback: Recurrence Relation and its Solution « Prantik Maitra

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s