6
$\begingroup$

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.

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

4 Answers 4

12
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Nice and clear way to do it ! $\endgroup$ Jul 3 at 7:36
  • $\begingroup$ @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$. $\endgroup$
    – dxiv
    Jul 3 at 17:12
10
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 4 at 19:05
  • 1
    $\begingroup$ No worries! Btw, you can review concurrently with posting :-) $\endgroup$
    – orangeskid
    Jul 4 at 19:08
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.