Prove midpoint sequence converges to endpoint

Question

Given arbitrary real constants $a$ and $b$, let $x_1 = a$, $x_2 = b$, and $x_{n+2} = \frac{x_n + x_{n+1}}{2}$. Prove the series $\{x_n\}$ is Cauchy and find its limit (from Mattuck Analysis).

My solution is below. I request feedback on:

1. Is my solution correct?
2. The proof writing, given my approach
3. Is there a simpler or better approach?

---

i. Proof sequence is Cauchy

If there exists $n$ such that $x_n = x_{n+1}$, then $x_{n+2} = x_{n+1}$, and by induction, $x_{m>n} = x_{n}$, QED. We therefore assume no such $n$ exists. Therefore, for any $n$, either $[x_n, x_{n+1}]$ or $[x_{n+1}, x_n]$ is an interval containing $x_{n+2}$, which we'll call $i_n$. Interval $i_n$ contains $i_{n+1}$, and so by induction $\{i_n\}$ is a series of finite nested intervals each containing $x_n$. The length of $i_{n+1}$ is $1/2$ the length of $i_n$, tending to $0$, and therefore by the nested intervals theorem, $\{x_n\}$ has a limit and is a Cauchy sequence.

ii. Find its limit

It's limit is $b$. We first find a closed form for $x_n$, and then find its limit directly.

For $n > 0$, let $\alpha_n = 2n -7$ and $\beta_n = 2^{n-2}$. Then for $n \geq 4$, $x_n = \frac{\alpha_n a + (\beta_n - \alpha_n) b}{\beta_n}$, via induction using elementary algebra. The limit of $\alpha_n/\beta_n$ is $0$, and by elementary limit theorems, the limit of $x_n$ is $b$.

iii. Discussion

Note that my proof for ii obvates the need for i. Mattuck implies there is a simpler proof for ii that draws on i, but I couldn't find it.

The closed form shows that $x_n$ is a convex combination of $a$ and $b$, each term with increasing weight of $b$, and generalizes to any $\alpha$ and $\beta$ where $\lim \alpha/\beta = 0$.

For ii, I found the first several terms manually, guessed the pattern, and attempted to prove it via induction. I understand this to be a common approach. The algebra used in induction, while elementary, got messy and error prone. How would a seasoned mathematician handle it? Via software like Sage?

I omitted the details of the algebra used in ii, since it's messy but elementary. I likewise omitted manual computation of the first several terms needed for the induction hypothesis, for the same reason. I understand this to be the adopted convention in proof writing.

Suggestions appreciated!

Answer 1

$x_1=a\;,\;x_2=b\;.\quad\color{blue}{(*)}$

$x_{n+2}=\dfrac{x_n+x_{n+1}}2\;\;$ for all $\;n\in\mathbb{N}\;.\quad\color{blue}{(**)}$

We will look for sequences $\;x_n=x^n\;$ which satisfy $\;(**):$

$x^{n+2}=\dfrac{x^n+x^{n+1}}2$

$x^2=\dfrac{1+x}2$

$x=1\;\lor\;x=-\dfrac12\;.$

So there are two sequences which satisfy $\;(**)\;$ and they are:

$x’_{\,n}=1^n=1\;\;$ for all $\;n\in\mathbb{N}\;,$

$x’’_{\;n}=\left(-\dfrac12\right)^n\;\;$ for all $\;n\in\mathbb{N}\;.$

Moreover, for any $\;\lambda\;,\mu\in\mathbb{R}\;,\;$ the sequences

$x_n=\lambda x’_{\,n}+\mu x’’_{\;n}=\lambda+\mu \left(-\dfrac12\right)^n\quad\forall\;n\in\mathbb{N}$

also satisfy $\;(**)\;.$

Now we will get the values of $\;\lambda\;$ and $\;\mu\;$ which satisfy $\;(*)\;.$

$\begin{cases} \lambda-\dfrac12\mu=a\\ \lambda+\dfrac14\mu=b \end{cases}$

$\begin{cases} \lambda=\dfrac{a+2b}3\\ \mu=\dfrac{4(b-a)}3 \end{cases}$

Therefore the sequence which satisfies $\;(*)\;$ and $\;(**)\;$ is :

$x_n=\dfrac{a+2b}3+\dfrac{4(b-a)}3\left(-\dfrac12\right)^n\;\;$ for all $\;n\in\mathbb{N}\;.$

Since $\;\exists\lim\limits_{n\to\infty}x_n=\dfrac{a+2b}3\in\mathbb{R}\;,\;$ then

$\big\{x_n\big\}_{n\in\mathbb{N}}\;$ is a Cauchy sequence.

Answer 2

The limit is not $b$. Take $a = 0, b = 1$. The first few terms are $0, 1, \frac{1}{2}, \frac{3}{4}, \frac{5}{8}, \dots$. The differences are $+1, -\frac{1}{2}, +\frac{1}{4}, -\frac{1}{8}, \dots$. So $\lim_{n \to \infty}x(n)$ is a geometric series with initial term $1$ and ratio $-\frac{1}{2}$. Therefore $\lim_{n \to \infty}x(n) = \frac{1}{1 - -\frac{1}{2}} = \frac{2}{3}$. When $a$ and $b$ are arbitrary we get the similar result $a + \frac{2}{3}(b - a)$.

This linear recurrence is easy to solve using a standard ansatz $x(n) = r^n$. Plugging this into the recurrence gives a polynomial $r^2 - \frac{1}{2}r - \frac{1}{2} = 0$. This has solutions $r = -\frac{1}{2}$, $r = 1$. So the general solution of the recurrence is any linear combination of these: $x(n) = C_1(-\frac{1}{2})^n + C_2$. Then you can plug in initial conditions $x(1) = a, x(2) = b$ to solve for $C_1$ and $C_2$. The limit is $C_2$ since $\lim_{n \to \infty}(\frac{1}{2})^n = 0$.

Answer 3

Since Mason's answer addresses all other parts of the question, let me focus on the following two:

Mattuck implies there is a simpler proof for ii that draws on i, but I couldn't find it.

How would a seasoned mathematician handle it?

I'm not a seasoned mathematician myself, but I would start exactly as Mason did - by considering the simplest example of the sequence $(y_n)$ satisfying the same relation $y_{n+2} = \frac{y_n+y_{n+1}}{2}$ but with $y_1 = 0$ and $y_2 = 1$ (which corresponds to taking $a=0$ and $b=1$). The general sequence can then be recovered as $$ x_n = (b-a) y_n + a. $$ It should be intuitive that $(x_n)$ and $(y_n)$ have an affine relation, and indeed it's trivial to check that the relation above guarantees $x_1=a$, $x_2=b$ and $x_{n+2} = \frac{x_n+x_{n+1}}{2}$. If you look at $(y_n)$ long enough, you may find that $y_n \to \frac{2}{3}$ and hence $x_n \to \frac{1}{3}a + \frac{2}{3}b$.

---

But what if (for some reason) we are unable to establish the limit of $(y_n)$? Well, by (i) we still know that a finite limit exists, so let's call it $\gamma$. Then $x_n \to (1-\gamma)a + \gamma b$, but it's not very useful unless we know the value of $\gamma$.

However, consider the following sequence: $$ y_2,y_3,y_4,y_5,\ldots = 1,\frac 12, \frac 34, \frac 58, \ldots $$ Of course it converges to $\gamma$, but at the same time it has the same form as $x_n$. Instead of $a$ and $b$, it starts from $1$ and $\frac 12$, so the same argument as before tells us that $$ \lim_{n \to \infty} y_{n+1} = (1-\gamma) \cdot 1 + \gamma \cdot \frac 12, $$ Comparing this to $\gamma$, we see that $\gamma = \frac 23$.