Solving Linear Recurrence Relations

This article follows on from my previous post of June 10th 2020 titled Fibonacci-like Sequences. I owe a debt of gratitude to Niloufar Shafiei who has posted an excellent PDF about solving linear recurrence relations. He treats both linear homogeneous recurrences and linear non-homogeneous recurrences but it is only the former that I'll concern myself with in this post.

With a linear recurrence, each term of a sequence is a linear function of earlier

terms in the sequence. An example would be:$$a_n=a_{n-1}+a_{n-2}+1$$However, this is not homogenous, because the last term, 1, does not involve an earlier term of the sequence. An example of a linear homogenous recurrence would be:$$a_n=a_{n-1}+2a_{n-2} \text{ with }a_0=1 \text{ and }a_1=5$$This corresponds to the quadratic:$$x^2=x+2 \text{ so that }x^2-x-2 = (x-2)(x+1)$$This equals 0 when \(x=2\) or \(x=-1\).

The PDF referred to earlier shows that the \(n\)-th term can be written in a form that is a linear combination of the two solutions:$$ \alpha_1(2^n)+\alpha_2(-1)^n \text{ where } \alpha_1 \text{ and } \alpha_2 \text{ are constants to be determined}$$The values of \(\alpha_1 \text{ and } \alpha_2 \) can be determined from the initial conditions. When we substitute for \(n=0\) and \(n=1\), this means that:$$\alpha_1+\alpha_2=1 \text{ and } 2 \alpha_1-\alpha_2=5$$Solving this pair of equations, we find \( \alpha_1=2\) and \( \alpha_2=-1\) and thus \(a_n\) can be written as:$$a_n=2^{n+1}-(-1)^n \text{ for } n \ge 0$$The dominant term of course is \(2^n\) and so:$$\lim_{n -> \infty}\frac{a_{n+1}}{a_n}=2$$The first ten terms of this sequence are (SageMathCell permalink):

1, 5, 7, 17, 31, 65, 127, 257, 511, 1025, 2047, 4097

If the quadratic associated with the recurrence relation has a repeated root, then a slightly different approach is required. For example, let's consider the recurrence:$$a_n=6a_{n-1}-9a_{n-2} \text{ with } a_0=1 \text{ and } a_1=9$$The quadratic that arises is:$$x^2=6x-9 \text{ or } x^2-6x+9=(x-3)^2$$The repeated root here is \(x=3\) and Niloufar Shafiei in his PDF shows that in this case, the solution is:$$\alpha_1(3)^n+\alpha_2 n(3)^n \text{ or } 3^n(\alpha_1+\alpha_2n)$$Again, we get two equation in two unknowns and in this case, after applying the initial conditions, the solution is \(\alpha_1=1\) and \(\alpha_2=2\). Thus \(a_n\) can be written as:$$a_n=3^n(1+2n) \text{ for } n \ge 0$$The dominant term is \(3^n\) and so:$$\lim_{n -> \infty}\frac{a_{n+1}}{a_n}=3$$The first ten elements of the sequence are (SageMathCell permalink):

1, 9, 45, 189, 729, 2673, 9477, 32805, 111537, 373977, 1240029, 4074381

So this is the essential idea. Niloufar Shafiei in his PDF has plenty more examples that are easy to understand and well-presented. There is a lot more to delve into regarding recurrence equations and I'm sure I'll be writing more about them in the future.