# Sequence with a contraction mapping of the sum

Consider a continuous function $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$ with the following property. There exists $c \in (0,1)$ such that for all $x,y \in \mathbb{R}^n$ it holds that $\left\| f(x) - f(y) \right\| \leq c \left\| x-y \right\|$, where $\left\| \cdot \right\|$ is the Euclidean norm.

From Banach's fixed-point theorem, we know that, for any $x^{(0)} = x_0 \in \mathbb{R}^n$, the sequence $$x^{ (k+1) } := f \left( x^{ (k) } \right)$$ converges to the unique fixed-point $\bar{x}$ of $f$, i.e. $\lim_{ k \rightarrow \infty } f( x^{(k)} ) = \bar{x} = f( \bar{x} )$.

Now consider $y^{ (0) } = x_0$ are the sequence $$y^{ (k) } := f \left( \frac{1}{k} \sum_{i=0}^{k-1} y^{(i)} \right).$$ For instance, $y^{(1)} = x^{(1)} = f(x_0)$, $y^{(2)} = f\left( \frac{1}{2}\left(x_0 + f(x_0) \right) \right)$, $y^{(3)} = f \left( \frac{1}{3}\left( x_0 + f(x_0) + f\left( \frac{1}{2}\left(x_0 + f(x_0) \right) \right) \right) \right)$.

What happens to $\lim_{k \rightarrow \infty} y^{(k)}$? Does it converge to some point? In particular to $\bar{x}$?

• You mean, there exist $c \in (0,1)$ and some norm $\| \cdot \|$ such that for all $x, y \ldots$. – Robert Israel Nov 26 '13 at 22:02
• Assuming what Robert suggested is the correct interpretation, we have $\lim\limits_{k\to\infty} y^{(k)} = \overline{x}$. – Daniel Fischer Nov 26 '13 at 22:03
• Yes, thanks. Let me slightly rephrase it then. – user693 Nov 26 '13 at 22:03
• Dear Daniel, thanks for the tip. I am also wondering about this, but I was not able to prove it. Can you give me a hint? – user693 Nov 26 '13 at 22:04
• Sure. Let me play a bit to see if I find something nice to show it, or whether the crude argument must suffice. – Daniel Fischer Nov 26 '13 at 22:14

## 1 Answer

Let $z_k =\displaystyle \dfrac{1}{k} \sum_{i=0}^{k-1} y^{(i)}$, Thus $$z_k = \dfrac{1}{k} (y^{(k-1)} + (k-1) z_{k-1}) = \dfrac{1}{k} \left(f(z_{k-1}) + (k-1) z_{k-1} \right)$$ while $$\overline{x} = \dfrac{1}{k} (f(\overline{x}) + (k-1) \overline{x})$$ and so

\eqalign{ \|z_k - \overline{x}\| &\le \dfrac{1}{k} \left\|f(z_{k-1}) - f(\overline{x})\right\| + \dfrac{k-1}{k} \left\| z_{k-1} - \overline{x}\right\|\cr &\le \dfrac{c + k-1}{k} \|z_{k-1} - \overline{x}\|}

Since $\sum_{k=1}^\infty 1/k = \infty$, $\prod_{k=1}^\infty (1 - (1-c)/k) = 0$, so $\|z_k - \overline{x}\| \to 0$.

• Thanks a lot for the solution. You have shown that $\frac{1}{k} \sum_{i=0}^{k-1} y^{(i)} \rightarrow \bar{x}$. Why this implies that $y^{(k)} \rightarrow \bar{x}$? – user693 Nov 26 '13 at 22:41
• $y^{(k)} = f(z_k)$ and $f$ is continuous. – Robert Israel Nov 26 '13 at 22:42
• Ok, thanks. So $\lim_{k \rightarrow \infty} y^{(k)} = \lim_{k \rightarrow \infty} f( z_k ) = f\left( \lim_{k \rightarrow \infty} z_k \right) = f( \bar{x} ) = \bar{x}$. – user693 Nov 26 '13 at 22:44
• Why does it hold that $\prod_{k=1}^{\infty} 1 - (1-c)/k$ is equal to $0$? – user693 Nov 27 '13 at 8:39
• Limit comparison test of $\sum_k -\log(1 - (1-c)/k)$ and $\sum_k 1/k$. More generally, there's a "well-known" theorem on infinite products: if $0 \le u_n < 1$, then $\prod_n (1 - u_n) > 0$ iff $\sum_n u_n < \infty$. – Robert Israel Nov 28 '13 at 4:21