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:$$\underset{n->\mathrm{\infty }}{lim}\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 }_{2}n)$$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:$$\underset{n->\mathrm{\infty }}{lim}\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.