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$$