A general linear recurrence relation is a recurrence relation with the form shown below:
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:
The first equation above is also known as a homogeneous linear recurrence relation, since it does not contain the 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:
The characteristic equation will be in the form:
By solving the characteristic equation, we can obtain solutions (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:
where are coefficients to be determined. These coefficients can be determined by substituting different values of (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 where 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 be a sequence which satisfies the conditions . Derive the general term for the sequence .
The above recurrence relation is a linear recurrence relation of second order (meaning is dependent on two preceding values and ). The characteristic equation of the sequence is . Solving the equation, we obtain the solutions
Hence, the general term of the solution is in the form
Plugging the values for , we obtain the following system of simultaneous equations:
This gives us the values of and , which are
Upon simplification, we obtain the general formula for Fibonacci sequence (also known as Binet’s formula)
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 , where is the solution of the corresponding homogeneous linear recurrence while is a function which is similar to the form of . I will use the following example to illustrate the technique:
Solve the recurrence relation given
The corresponding linear homogeneous recurrence relation of the above equation is . It’s general solution is for some constant to be determined later. As such, . Right now, we need to determine which should be in the form of since is a quadratic function.
Now, is supposed to satisfy the recurrence relation. As such, we have:
By rearranging and comparing coefficients, we obtain the following system of equations:
Solving the above system, we obtain and . This makes it clear that and hence . By plugging the value of , we finally obtain . Hence the final answer is .
Not all recurrence relations can be solved like this. Coincidentally, we are able to set 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:
- (USAMO 1973 P2) Let and denote two sequences of integers defined as follows:
Prove that, except for the ’1′, there is no term which occurs in both sequences
- (SMO(O)1999 P8) For each positive integer , let denote the number of -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 in terms of .
- (IMO 1979 P6) Let and be opposite vertices of an octagon. A frog starts at vertex . From any vertex except it jumps to one of the two adjacent vertices. When it reaches it stops. Let be the number of distinct paths of exactly jumps ending at . Prove that