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

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.

• Hint: it's a linear recurrence, and the characteristic polynomial has three easy roots.
– dxiv
Jul 3 at 2:11

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\,$$.

• Nice and clear way to do it ! Jul 3 at 7:36
• @ClaudeLeibovici Thanks. This was a case where the "trick" worked naturally. In general, a homogeneous recurrence of order $n$ with characteristic polynomial $p(t)$ having a simple root $t=a$ can be reduced to a non-homogeneous recurrence of order $n-1$ with polynomial $p(t)/(t-a)$ using similar telescoping, which reduces to direct summation when $a=1$.
– dxiv
Jul 3 at 17:12

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.

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})\cdot ( x^{n-1} - s_1 x^{n-2} + s_2 x^{n-3} - \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-1} - s_1 x_{n-2} + s_2 x_{n-3} - \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}$$

• Fellow math exchangers, thank you for enlighten me. I decided to carry out a good review of linear recurrences before posting new questions. Best Regards. Jul 4 at 19:05
• No worries! Btw, you can review concurrently with posting :-) Jul 4 at 19:08

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).