Limit of sequence given by $x_{n} = \frac{x_{n-2}+x_{n-3}}{2}$?

Question

Let $x_1,x_2,x_3\in\mathbb{R}$ be three distinct real numbers. I am interested in the convergence of the sequence $$ x_{n} = \frac{x_{n-2}+x_{n-3}}{2},\quad n = 4,5,\ldots $$ ie, $$ x_{4} = \frac{x_{2}+x_{1}}{2},\quad x_{5} = \frac{x_{3}+x_{2}}{2},\quad x_{6} = \frac{x_{4}+x_{3}}{2},\quad\cdots $$ Please note that, although related to, this is not a recursive averaging sequence with two initial values, as described and studied elsewhere --- see, for instance, Smith, Scott G. "Recursive Averaging". The Mathematics Teacher, Vol. 108, No. 7 (March 2015), pp. 553-557.

In the present case, convergence is easily verified by noting that $$ \big|\,x_{n}-x_{n-1}\,\big| = \big|\frac{x_{n-2}+x_{n-3}}{2}-\frac{x_{n-3}+x_{n-4}}{2}\big| = \big|\,\frac{1}{2} (x_{n-2}-x_{n-4})\,\big| = \big|\,\frac{1}{2^{\,n-4}}\,\big|\cdot\big|\, x_{3}-x_{1}\,\big| $$ Therefore the sequence is Cauchy and hence it converges in $\mathbb{R}$.

However, I was not able to find the limit to where the sequence converges. Computer experiments carried out with several different sets of initial values suggest that this limit should be a linear combination of the those initial values, as occurs in the case mentioned above. Also, the results of these experiments point to the existence of (how many?) sub-sequences, all converging to the very same limit.

I would appreciate some help in the analysis of this problem.

Answer 1

Once the convergence has been proved, one thing to try is to pass the recurrence relation to the limit, in hope that it can then be solved for the limit $\,L\,$. Here, though, this results in the tautology $\,L=L\,$ which is useless for the purpose of calculating the limit. However, in such cases there is a fair chance that there is some form of telescoping "hidden" in the recursion, which can provide an alternate way to find the limit without actually solving the recurrence.

For a linear recurrence like the one here, this amounts to adding up the consecutive relations:

$$ \require{cancel} \begin{align*} 2x_{n} &= \color{red}{\bcancel{x_{n-2}}} + \color{blue}{\cancel{x_{n-3}}} \\ 2x_{n-1} &= \color{blue}{\cancel{x_{n-3}}} + \color{green}{\cancel{x_{n-4}}} \\ \color{red}{\bcancel{2}}x_{n-2} &= \color{green}{\cancel{x_{n-4}}} + \cancel{x_{n-5}} \\ \color{blue}{\cancel{2x_{n-3}}} &= \cancel{x_{n-5}} + \cancel{x_{n-6}} \\ \color{green}{\cancel{2x_{n-4}}} &= \cancel{x_{n-6}} + \cancel{x_{n-7}} \\ \dots \\ \cancel{2x_7} &= \cancel{x_5} + \color{brown}{\cancel{x_4}} \\ \cancel{2x_6} &= \color{brown}{\cancel{x_4}} + x_3 \\ \cancel{2x_5} &= x_3 + x_2 \\ \color{brown}{\cancel{2x_4}} &= x_2 + x_1 \\ \hline \\2 x_n + 2x_{n-1}+x_{n-2} &= x_1 + 2x_2 + 2x_3 \end{align*} $$

Then, passing to the limit with $\,x_n, x_{n-1}, x_{n-2} \to L\,$ gives $\,5L = x_1 + 2x_2 + 2x_3\,$.

Answer 2

For the linear recurrence $$x_{n} = \frac{x_{n-2}+x_{n-3}}{2}$$ the characteristic polynomial is $$r^3=\frac {r+1}2 \implies r_1=1 \qquad r_2=-\frac {1+i} 2\qquad r_3=-\frac {1-i} 2$$

and, as usual, $$x_n=c_1 + c_2 r_1^n+c_3 r_2^n$$

Using $x_1=a$, $x_2=b$, $x_3=c$, this would give $$x_n=A_n \,a+B_n\, b+C_n\, c$$ with $$A_n=\frac{1}{5} \left(1-(3-i) \left(-\frac{1}{2}-\frac{i}{2}\right)^n-(3+i) \left(-\frac{1}{2}+\frac{i}{2}\right)^n\right)$$ $$B_n=\frac{1}{5} \left(2-(1+3 i) \left(-\frac{1}{2}-\frac{i}{2}\right)^n-(1-3 i) \left(-\frac{1}{2}+\frac{i}{2}\right)^n\right)$$ $$C_n=\frac{1}{5} \left(2+(2+i) (-1-i)^n 2^{1-n}+(2-i) (-1+i)^n 2^{1-n}\right)$$

Using Euler's formulae $$A_n=\frac{1}{5}\left(1+2^{1-\frac{n}{2}} \sin \left(\frac{3 \pi n}{4}\right)-3\ 2^{1-\frac{n}{2}} \cos\left(\frac{3 \pi n}{4}\right) \right)$$ $$B_n=\frac{1}{5}\left(2-3\ 2^{1-\frac{n}{2}} \sin \left(\frac{3 \pi n}{4}\right)-2^{1-\frac{n}{2}} \cos \left(\frac{3 \pi n}{4}\right) \right)$$ $$C_n=\frac{1}{5}\left(2+2^{2-\frac{n}{2}} \sin \left(\frac{3 \pi n}{4}\right)+2^{3-\frac{n}{2}} \cos \left(\frac{3 \pi n}{4}\right) \right)$$ and now, make $n \to \infty$ for a very simple result.

Answer 3

The characteristic equation of the linear recurrence is

$$\lambda^3 - \frac{1}{2}\lambda-\frac{1}{2} = 0$$ with roots $\lambda_1=1$, $\lambda_{2,3} = \frac{1}{\sqrt{2}}\cdot(-\frac{1}{\sqrt{2}} \pm \frac{i}{\sqrt{2}})$. There exist unique $a$, $b$, $c$ such that for all $n \ge 0$ we have

$$x_n = a \cdot 1^n + b \cdot \lambda_2^n + c \cdot \lambda_3^n$$

Since $|\lambda_{2,3}|= \frac{1}{\sqrt{2}}< 1$, we have $$\lambda_2^n \to 0, \ \ \lambda_3^n \to 0$$ for $n \to \infty$. We conclude that $x_n \to a$. Now we only need to obtain $a$ from the equalities

$$x_0 = a + b + c \\ x_1 = a + b \lambda_2 + c \lambda_3\\ x_2 = a + b \lambda_2^2 + c \lambda_3^3$$ We get with Cramer's rule

$$ a = \frac{\left| \begin{matrix} x_0 & 1 & 1 \\ x_1 & -\frac{1}{2} + \frac{i}{2} & -\frac{1}{2} - \frac{i}{2}\\ x_2 & (-\frac{1}{2} + \frac{i}{2})^2 & (-\frac{1}{2} - \frac{i}{2})^2 \end{matrix} \right |} {\left| \begin{matrix} 1 & 1 & 1 \\ 1 & -\frac{1}{2} + \frac{i}{2} & -\frac{1}{2} - \frac{i}{2}\\ 1 & (-\frac{1}{2} + \frac{i}{2})^2 & (-\frac{1}{2} - \frac{i}{2})^2 \end{matrix} \right |} = \frac{1}{5}(x_0 + 2 x_1 + 2 x_2)$$

$\bf{Added:}$ Since we are dealing with linear recurrences it's worth getting comfortable with determinants of the form

$$D(x_0, x_1, \ldots x_{n-1}) \colon = \left| \begin{matrix} x_0 & 1 & \ldots &1 \\ x_1 & \mu_2& \ldots& \mu_{n} \\ x_2 & \mu_2^2& \ldots & \mu_{n}^2 \\ \ldots& & & \ldots \\ x_{n-1} & \mu_2^{n-1} & \ldots & \mu_{n}^{n-1} \end{matrix} \right |$$

Note that when $x_k = x^k$ for $0\le k \le n-1$ we have a Vandermonde determinant, which equals $$V(x, \mu_2, \ldots, \mu_{n}) = V( \mu_2, \ldots, \mu_{n}) \cdot \prod_{i=2}^{n}( \mu_i - x)= \\ =(-1)^{n-1} V( \mu_2, \ldots, \mu_{n})\cdot (x-\mu_2)\cdot (x-\mu_{n}) = (-1)^{n-1} V( \mu_2, \ldots, \mu_{n+1})\cdot ( x^{n-1} - s_1 x^{n-} + s_2 x^{n-2} - \cdots)$$

It follows that the determinant with first column $(x_0, x_1, \ldots x_{n-1})$ equals

$$(-1)^{n-1} V(\mu_2, \ldots, \mu_{n+1}) \cdot ( x_n - s_1 x_{n-1} + s_2 x_{n-2} - \cdots)$$

Now when solving the system we have a quotient of such determinants $D$, the extra factor $(-1)^{n-1} \cdot V$ can be omitted. We get: the coefficient in front of a power $\mu_1^n$ equals

$$\frac{P(x)/(x-\mu_1)}{P'(\mu_1)}$$ where the numerator is considered "in the umbral sense".

Example with our problem at hand:

The characteristic polynomial equals $P(x)=x^3 - \frac{1}{2} x - \frac{1}{2}$.

1. For the numerator : divide $P(x)$ by $x-\mu_1= x-1$ and get $\frac{1}{2}(2 x^2 + 2 x + 1)$. This umbrally is $\frac{1}{2}(2 x_2 + 2x_1 + x_0)$.

2. For the denominator we have $P'(x) = 3 x^2 - \frac{1}{2}$ so $P'(1) = \frac{5}{2}$

3. Set up the fraction

$$a_1 = a =\frac{\frac{1}{2}(2 x_2 + 2 x_1 + x_0)}{\frac{5}{2}} = \frac{2 x_2 + 2 x_1 + x_0}{5}$$

Answer 4

You already received excellent answers, yet let me present a matricial approach (Fibonacci style) which might be of interest in smilar cases. $$ \begin{array}{l} x_n = \frac{{x_{n - 2} + x_{n - 3} }}{2}\quad \Rightarrow \\ \Rightarrow \quad \left( {\begin{array}{*{20}c} {x_n } \\ {x_{n - 1} } \\ {x_{n - 2} } \\ \end{array}} \right) = \left( {\begin{array}{*{20}c} 0 & {1/2} & {1/2} \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array}} \right)\left( {\begin{array}{*{20}c} {x_{n - 1} } \\ {x_{n - 2} } \\ {x_{n - 3} } \\ \end{array}} \right)\quad \Rightarrow \\ \Rightarrow \quad {\bf x}_n = {\bf A}\;{\bf x}_{n - 1} \\ \end{array} $$

The matrix $\bf A$ is (right) stochastic matrix and thus the matrix of a Markov chain.

It is easy to see that the eigenvalues are $$ 1 = e^{\,i0} ,\; - \left( {1 + i} \right)/2 = \frac{{\sqrt 2 }}{2}e^{ - i\frac{3}{4}\pi } ,\; - \left( {1 - i} \right)/2 = \frac{{\sqrt 2 }}{2}e^{i\frac{3}{4}\pi } $$ and to find the relevant eigenvectors. In particular that the eigenvector corresponding to the eigenvalue $1$ is $$\bf v =(1,1,1)^T$$ and the theory of Markov chain assures us that $$ {\bf v} = {\bf A}\;{\bf v} $$ is the stable vector to which the chain is going to converge, once we start from any "probabilistic" vector, i.e.
whose components are non-negative and sum to one. Otherwise, you can just reduce to that by a suitable scaling diagonal matrix.

You can get more details on the convergence chain by diagonalizing $\bf A$., but is clear that the remaining two eigenvalues are declining as $2^{-n/2}$ (or $2^{-(n-3)/2}$, or $2^{-(n-4)/2}$ depending on the starting point).