Showing posts with label repeated roots. Show all posts
Showing posts with label repeated roots. Show all posts

Tuesday, 16 June 2020

Solving Linear Recurrences

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.