More on Linear Recurrence Relations

This post is a follow on from an earlier post, titled Solving Linear Recurrence Relations of June 16th 2020, in which I dealt only with polynomials having real roots. Here I look at an example of a polynomial with one real root and two complex roots.

Suppose we have the following recurrence: $$a_n=a_{n-1}-a_{n-2}+a_{n-3} \text{ with } a_0=1, a_2=2, a_3=3$$ This corresponds to $x^3=x^2-x+1$ and thus we can write:

$$\begin{align} P(x)&=x^3-x^2+x-1\\ &=x^2 \,(x-1)+1 \, (x-1)\\ &=(x^2+1)(x-1) \end{align}$$ with solutions of $x=1, \pm \, i$ when $P(x)=0$. The $n$-th term can be written as a linear combination of these three solutions and thus: $$a_n=A \cdot (1)^n+B \cdot i^n+C \cdot (-i)^n \text{ with } A, B, C \text{ constants }$$ We apply the initial conditions then to find the values of $A, B, C$ by creating three equations in the three unknowns: $$\begin{align} A+B+C&=1 \text{ when }n=0\\ A+B\,i-C \,i&=2 \text{ when }n=1\\ A-B-C&=3 \text{ when }n=2 \end{align}$$ Solving these we find that: $$\begin{align} A&=\frac{2}{5}\\ B&=-\frac{i+2}{10}\\ C&=\frac{i-2}{10} \end{align}$$ This means that $a_n$ is then given by: $$a_n=\frac{2^{n+2}-i^{\,n}\,((i+2)-(i-2) \,(-1)^n)}{10}$$ This satisfies the original conditions and will generate all terms: 0, 1, 2, 3, 6, 13, 26, 51, 102, 205, 410, 819, 1638, 3277, 6554, 13107, 26214, 52429, 104858, 209715, 419430, 838861, 1677722, ...

Even though the formula contains $i$'s, they always cancel out to produce real numbers. My interest in this topic was rekindled when I looked at my diurnal age (26200) and found that it could be generated by the following linear homogenous recurrence: $$a(n)=a(n-1)+a(n-3) \text{ with } a(0)=3, a(1)=1, a(2)=4 \text{ and } n≥3$$ This lead to a polynomial with one real root and two complex roots, namely: $$P(x) = x^3 - x^2 - 0 \cdot x - 1 = x^3 - x^2 - 1$$ However, the roots are nasty and so I chose to deal with a simpler but similar polynomial in this post. 

To see how the terms of the first sequence $$a_n=a_{n-1}-a_{n-2}+a_{n-3}$$  can be generated from the initial values $$a_0=1, a_2=2, a_3=3$$ or from the formula for the $n$-th term $$a_n=\frac{2^{n+2}-i^{\,n}\,((i+2)-(i-2) \,(-1)^n)}{10}$$ follow this SageMathCell permalink. Clearly, we also have: $$\lim_{n \to \infty} \frac{a_{n+1}}{a_n}=2$$