A sequence $A(n)$ that satisfies $A(n) = \frac{A(n-1) + A(n-2) + A(n-3)}{3}$

Question

Show that there exist $c_1, c_2, \lambda_1, \lambda_2 \in \mathbb{C}$ such that $A(n)= c_1\lambda_1^n+c_2\lambda_2^n + c_3$ for all $n \geq0$

Hint: The system that defines $A(n)$ is linear of third order and the characteristic polynomial has 3 different roots, one of them being equal to 1. Adapt to a linear system of second order with two different roots.

If $|\lambda_1| = |\lambda_2| <1$, show that

$$\lim A(n) = \frac{1}{6}A(0)+\frac{1}{3}A(1)+\frac{1}{2}A(2)$$

---

I can’t seem to see how to adapt the result to a linear system of second order with two different roots. I have calculated the characteristic polynomial and found that there are indeed 3 roots, one of them being 1 and the other two being complex roots, one is the conjugate of the other. Also, I can’t really see where do I have to go, any hints or help are very much appreciated.

Answer 1

Note first that a solution of the form $A(n)=c\lambda^n$ exists iff $\lambda^3=\frac{\lambda^2+\lambda+1}{3}$. This cubic polynomial has three distinct roots, $1,\,\frac{-1\pm i\sqrt{2}}{3}$. These span a $3$-dimensional vector space of the solutions; and the solutions only form a $3$-dimensional vector space, because three consecutive terms completely specify the sequence. Hence the solution is $c_1\left(\frac{-1+i\sqrt{2}}{3}\right)^n+c_2\left(\frac{-1-i\sqrt{2}}{3}\right)^n+c_31^n$ for some constants $c_k$. Since the resulting $\lambda_1,\,\lambda_2$ are each of modulus $\frac{1}{\sqrt{3}}<1$, $\lim_{n\to\infty}A(n)=c_3$. You can express $A(0),\,A(1),\,A(2)$ in terms of the $c_k$, then verify the desired expression for the limit is correct.

As for adaptation to a second-order system, define $B_n:=A(n+1)-A(n)$ so $$B_{n+2}=\frac{A(n)+A(n+1)-2A(n+2)}{3}=-\frac{B_n+2B_{n+1}}{3}.$$

Answer 2

Rewrite the equation you have as

$$3A_n=A_{n-1}+A_{n-2}+A_{n-3}$$ and set $B_n = A_n-A_{n-1}$ so that $A_{n-3}=A_{n-2}-B_{n-2}$ etc

Then $3A_n=A_{n-1}+A_{n-2}+A_{n-2}-B_{n-2}=A_{n-1}+2A_{n-1}-2B_{n-1}-B_{n-2}=3A_n-3B_n-2B_{n-1}-B_{n-2}$ whence

$$3B_n+2B_{n-1}+B_{n-2}=0$$ as if by magic.

If $\lambda$ is one of the roots of the characteristic equation so that $x-\lambda$ is a factor of polynomial, you will find that $B_n=A_n-\lambda A_{n-1}$ will reduce the degree of the equation by $1$ and this is easy enough to show in general. Here $\lambda =1$ is the root you take, and I think this is what may be meant by adapting to a linear system of order $2$.