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{array}{rl}P(x)& =x^3-x^2+x-1\\ & =x^2(x-1)+1(x-1)\\ & =(x^2+1)(x-1)\end{array}$$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{array}{rl}A+B+C& =1\text{ when }n=0\\ A+Bi-Ci& =2\text{ when }n=1\\ A-B-C& =3\text{ when }n=2\end{array}$$Solving these we find that:$$\begin{array}{rl}A& =\frac{2}{5}\\ B& =-\frac{i+2}{10}\\ C& =\frac{i-2}{10}\end{array}$$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\ge 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:$$\underset{n\to \mathrm{\infty }}{lim}\frac{a_{n+1}}{a_n}=2$$