Here's my question:
Take three numbers $x_1$, $x_2$, and $x_3$, and form the successive running averages $$x_n = \frac{x_{n-3} + x_{n-2} + x_{n-1}}{3}$$ starting with $x_4$. Prove that $$\lim_{n \to \infty} x_n = \frac{x_1 + 2x_2 + 3x_3}{6}$$
So I know how to do this by setting up the transition matrix and diagonalizing it to figure out what the transition matrix looks like when raised to a really high power. However, I'm curious if anyone has a different approach. Thanks in advance!
If you absolutely don't want to diagonalize, you could do something like this:
First convince yourself that the sequence must converge. For example, instead of having a sequence, imagine just having three numbers and successively replacing one of them with the average of all. If you keep the details straight, you can then see that the maximum of the numbers cannot increase and the minimum cannot decrease, and the distance between the maximum and minimum shrinks geometrically at least once per three iterations. So the numbers must converge towards something.
Next, since the recurrence is linear, a linear combination of two solution sequences is again a solution. So if we know the limit of the sequence that starts $(1,0,0)$ is $A$, the limit of the sequence that starts $(0,1,0)$ is $B$, and the limit of the sequence that starts $(0,0,1)$ is $C$, then if we start off at a general triple $(x,y,z)$ the limit must be $Ax+By+Cz$.
However, if we do one step of the recurrence then we have three new "most recent" numbers, and the rest of the computation doesn't care that those were not the numbers we started with. So we must have $$ Ax+By+Cz = Ay+Bz+C\frac{x+y+z}3 $$ And this is true for all $x,y,z$, so the two sides of this equation is the same polynomial in $x,y,z$. Equating coefficients we find $$ A = C/3 \qquad \qquad B=A+C/3 \qquad \qquad C = B+C/3 $$ which doesn't completely determine the system but does give us $B=2A$, $C=3A$. We can get one additional equation between the coefficients by noting that the $(1,1,1)$ sequence obviously converges to $1$, so $A+B+C=1$, giving $$ A=1/6 \qquad \qquad B=1/3 \qquad\qquad C=1/2 $$
Let $v_n=(x_n,x_{n-1},x_{n-2})$, let $$A=\pmatrix{1/3&1/3&1/3\cr1&0&0\cr0&1&0\cr}$$ Then $Av_n=v_{n+1}$. The matrix $A$ is row-stochastic and regular, so its dominant eigenvalue is $1$. A left-eigenvector for the eigenvalue $1$ is a nonzero element of the left-nullspace of $$A-I=\pmatrix{-2/3&1/3&1/3\cr1&-1&0\cr0&1&-1\cr}$$ The vector $(3,2,1)$ is a basis for the left-nullspace. Dividing by $6$ gives the unique eigenvector that's a probability vector, $w=(1/2,1/3,1/6)$, which tells you, without diagonalizing, that $A^n$ converges to the matrix whose rows are all $w$.
To solve $$ x_n=\tfrac13(x_{n-1}+x_{n-2}+x_{n-3})\tag1 $$ We consider the characteristic equation $x^3-\tfrac13x^2-\tfrac13x-\tfrac13=0$, which has roots $$ \left\{1,\frac{-1+i\sqrt2}3,\frac{-1-i\sqrt2}3\right\}\tag2 $$ The solution to $(1)$ is therefore of the form $$ x_n=c_0+c_1\color{#C00}{\left(\frac{-1+i\sqrt2}3\right)^n}+c_2\color{#090}{\left(\frac{-1-i\sqrt2}3\right)^n}\tag3 $$ Since $\left|\frac{-1+i\sqrt2}3\right|=\left|\frac{-1-i\sqrt2}3\right|=\frac1{\sqrt3}$, $\lim\limits_{n\to\infty}x_n=c_0$.
Note that $$ \color{#C00}{\begin{bmatrix}-1-i\sqrt2\\1\\\frac{-1+i\sqrt2}3\end{bmatrix}}\times\color{#090}{\begin{bmatrix}-1+i\sqrt2\\1\\\frac{-1-i\sqrt2}3\end{bmatrix}} =\begin{bmatrix}-i\frac{2\sqrt2}3\\-i\frac{4\sqrt2}3\\-i2\sqrt2\end{bmatrix} =-i\frac{2\sqrt2}3\,\begin{bmatrix}1\\2\\3\end{bmatrix}\tag4 $$ That is, $\begin{bmatrix}1&2&3\end{bmatrix}$ is perpendicular both to $\left[\left(\frac{-1+i\sqrt2}3\right)^k\right]_{k=n-1}^{n+1}$ and $\left[\left(\frac{-1-i\sqrt2}3\right)^k\right]_{k=n-1}^{n+1}$
Therefore, we get that for any $3$ consecutive terms, $$ \bbox[5px,border:2px solid #C0A000]{\lim\limits_{n\to\infty}x_n=c_0=\frac{x_{n-1}+2x_n+3x_{n+1}}6}\tag5 $$
A Simple Verification of $\boldsymbol{(5)}$ $$ \begin{align} \frac{\color{#C00}{3x_{n+1}}+\color{#090}{2x_n+x_{n-1}}}6 &=\frac{\color{#C00}{x_n+x_{n-1}+x_{n-2}}+\color{#090}{2x_n+x_{n-1}}}6\\ &=\frac{3x_n+2x_{n-1}+x_{n-2}}6\tag6 \end{align} $$ and simply take the limit of $(6)$.
