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.