<p>The OP correctly identified a mistake here. Since the author claims monotonicity for a general function, let's disprove it for the simple linear case.
Consider</p>

<p>$$x_{t+1} = g(x_t) = -0.5x_t$$</p>

<p>This satisfies all the requirements and conditions stated by the author, and also that the derivative is smaller than unity in absolute values $\forall x$. But it converges with "damped oscillations", and so it is not monotonic since, say, </p>

<p>$$x_0 = -3 &lt; 0 = x^*$$
$$x_1 = 1.5$$
$$x_2 = -0.75$$
etc</p>

CC BY-SA 3.0
2016-10-10T10:23:03.613Z
I believe you meant damped oscillations (reduced over time) rather than dumped
Three Diag
CC BY-SA 3.0
2016-10-10T23:14:00.650Z
@ThreeDiag Thanks for spotting this. Fixed.
Alecos Papadopoulos
CC BY-SA 3.0
2016-09-23T19:03:46.980Z
2016-10-10T23:13:40.480Z
2016-10-10T23:13:40.480Z
Alecos Papadopoulos
<p>Since the OP asked for a rigorous proof, here is one.</p>
<p>By Acemoglu's inequality in the first part of his proof, we can separate <span class="math-container">$\{x(t)\}_{t=0}^{\infty}$</span> into two subsequences, an increasing subsequence <span class="math-container">$\{x(t_{i})\}_{t_{i}\in I}$</span> bounded above by <span class="math-container">$x^{*}$</span> and a decreasing subsequence <span class="math-container">$\{x(t_{j})\}_{t_{j} \notin I}$</span> bounded below by <span class="math-container">$x^{*}$</span>. Indeed, we define <span class="math-container">$I$</span> to be the set <span class="math-container">$\{t \in \mathbb{N} \mid x(t)&lt;x^{*}\}$</span>. By Acemoglu's inequality, <span class="math-container">$s&gt;t$</span> implies <span class="math-container">$x(s)$</span> is strictly closer to <span class="math-container">$x^{*}$</span> than <span class="math-container">$x(t)$</span> is. Thus, since <span class="math-container">$x(t_{i})&lt;x^{*}$</span> for all <span class="math-container">$t_{i} \in I$</span>, <span class="math-container">$\{x(t_{i})\}_{t_{i}\in I}$</span>  is increasing. Similarly, <span class="math-container">$\{x(t_{j})\}_{t_{j} \notin I}$</span> is decreasing and bounded below by <span class="math-container">$x^{*}$</span></p>
<p>Assume that each of these subsequences is infinite. Then each converges to a limit, which we will denote by <span class="math-container">$y$</span> and <span class="math-container">$z$</span> respectively.</p>
<p>Note that it also follows from Acemoglu's inequality that <span class="math-container">$y=x^{*}-\epsilon$</span> and <span class="math-container">$z=x^{*}+\epsilon$</span> for some <span class="math-container">$\epsilon \geq 0$</span>. Indeed, suppose that this is not the case (we will show this generates a contradiction). For convenience, assume <span class="math-container">$\vert y -x^{*}\vert&lt;\vert z-x^{*}\vert$</span>. Define
<span class="math-container">$$\delta:=\vert z-x^{*}\vert-\vert y-x^{*}\vert&gt;0.$$</span>
Since <span class="math-container">$\lim_{i \to \infty}x(t_{i})=y$</span>, we can pick <span class="math-container">$t \in \mathbb{N}$</span> such that
<span class="math-container">$$\vert x(t)-y\vert&lt;\frac{\delta}{2}.$$</span>
The triangle inequality then tells us that
<span class="math-container">$$\vert x(t)-x^{*}\vert &lt;\vert y-x^{*}\vert+\frac{\delta}{2}.$$</span>
Now pick some <span class="math-container">$s \in \mathbb{N}$</span> such that <span class="math-container">$s &gt;t$</span> and <span class="math-container">$x(s)&gt;x^{*}$</span> (such an <span class="math-container">$s$</span> exists by our assumption that both the constructed subsequences are infinite). Since <span class="math-container">$x(s)&gt;z&gt;x^{*}$</span>, we have that
<span class="math-container">$$\vert x(s)-x^{*}\vert&gt;\vert z-x^{*}\vert.$$</span>
Thus,
<span class="math-container">$$\vert x(t)-x^{*}\vert &lt;\vert y-x^{*}\vert+\frac{\delta}{2}&lt;\vert z-x^{*}\vert &lt;\vert x(s)-x^{*}\vert.$$</span>
But since <span class="math-container">$s&gt;t$</span>, this contradicts Acemoglu's inequality.</p>
<p>Now we will consider the value of <span class="math-container">$g(y)$</span>. Since,
<span class="math-container">$$g(y)=g(\lim_{i \to \infty}x(t_{i}))=\lim_{i \to \infty}g(x(t_{i}))=\lim_{i \to \infty}x(t_{i}+1),$$</span>
we must have that <span class="math-container">$g(y)=y$</span> or <span class="math-container">$g(y)=z$</span>.</p>
<p>If <span class="math-container">$g(y)=z$</span>, then we must have that <span class="math-container">$y=z=x^{*}$</span> since if <span class="math-container">$y\neq x^{*}$</span>, we get a contradiction. Indeed, if <span class="math-container">$y \neq x^{*}$</span>, then Acemoglu's inequality implies that <span class="math-container">$g(y)$</span> is strictly closer to <span class="math-container">$x^{*}$</span> than <span class="math-container">$y$</span> is; but <span class="math-container">$y$</span> and <span class="math-container">$z$</span> are equidistant from <span class="math-container">$x^{*}$</span>. Thus <span class="math-container">$g(y)=y$</span> and similarly <span class="math-container">$g(z)=z$</span>. (If only one of the subsequences is infinite, we get this immediately.) But this implies that <span class="math-container">$y=z=x^{*}$</span>, as Acemoglu's inequality allows us to infer that if <span class="math-container">$y \neq x^{*}$</span>, then <span class="math-container">$g(y)$</span> is strictly closer to <span class="math-container">$x^{*}$</span> than <span class="math-container">$y$</span> is.</p>

CC BY-SA 4.0
2021-09-21T07:12:33.857Z
I'm not sure how you get to the claim that there are two monotone sequences whose limits are equally far from $x^\ast$. I think it would be good to be somwhat more specific where this comes from.
tdm
CC BY-SA 4.0
2021-09-21T09:44:11.057Z
Thanks for the suggestion @tdm. I've updated the proof with more detail on that claim.
Louis Becker
CC BY-SA 4.0
2021-09-21T04:05:01.160Z
2021-09-21T09:40:44.790Z
2021-09-21T09:40:44.790Z
Louis Becker
<p>I am reading Acemoglu's intro to modern economic growth. But I am having trouble understanding his proof to a theorem related with stability. Here is the theorem: 
<a href="https://i.sstatic.net/pr2NW.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/pr2NW.jpg" alt="enter image description here"></a></p>

<p>And here are some related definitions and theorems:
<a href="https://i.sstatic.net/5c891.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5c891.jpg" alt="enter image description here"></a>
<a href="https://i.sstatic.net/x4kBe.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/x4kBe.jpg" alt="enter image description here"></a></p>

<p>My question lies in his proof of corollary $2.1$. How did he show that the sequence $x(t)$ is monotone and bounded above by $x^*$? I think it is not enough to use that the derivative is less than $1$ and the distance to $x^*$ is shrinking to say $x(t)$ is monotone. Can someone give me some more details to understand the proof?</p>

<p>Thanks!</p>

CC BY-SA 3.0
2016-09-16T01:49:10.903Z
Given that $|a|<1$ and the linear difference is affine, ratio being less than 1 (dividing the RHS over to the left) is enough to get monotone. Try some examples.
VCG
CC BY-SA 3.0
2016-09-16T03:07:35.923Z
It only says the distance is decreasing, and it does not eliminate the case say $x(0)=1, x^*=3, x(1)=4, x(2)=2.5, x(3)=3.25...$, or even an extreme case that $x^*=1, x(2k-1)=\frac{1}{2}- \frac{1}{2k-1}, x(2k)=\frac{3}{2}+\frac{1}{2k}$, where $x(t)$ does not converge to $x^*$
ask
CC BY-SA 3.0
2016-09-16T03:16:50.923Z
And also we are in the non-linear case...
ask
<macroeconomics><difference-equations>
Rigorous proof needed: Acemoglu (Intro Growth) Corollary $2.1.2$
ask
# Rigorous proof needed: Acemoglu (Intro Growth) Corollary $2.1.2$

(Asked by: username_0 on 2016-09-16)

I am reading Acemoglu's intro to modern economic growth. But I am having trouble understanding his proof to a theorem related with stability. Here is the theorem:
[![enter image description here](https://i.sstatic.net/pr2NW.jpg)](https://i.sstatic.net/pr2NW.jpg)

And here are some related definitions and theorems:
[![enter image description here](https://i.sstatic.net/5c891.jpg)](https://i.sstatic.net/5c891.jpg)
[![enter image description here](https://i.sstatic.net/x4kBe.jpg)](https://i.sstatic.net/x4kBe.jpg)

My question lies in his proof of corollary $2.1$. How did he show that the sequence $x(t)$ is monotone and bounded above by $x^\*$? I think it is not enough to use that the derivative is less than $1$ and the distance to $x^\*$ is shrinking to say $x(t)$ is monotone. Can someone give me some more details to understand the proof?

Thanks!

**Tags:** macroeconomics, difference-equations
> **Comments:**
> **username_1**: Given that $|a|<1$ and the linear difference is affine, ratio being less than 1 (dividing the RHS over to the left) is enough to get monotone. Try some examples.  
> **username_0**: It only says the distance is decreasing, and it does not eliminate the case say $x(0)=1, x^*=3, x(1)=4, x(2)=2.5, x(3)=3.25...$, or even an extreme case that $x^*=1, x(2k-1)=\frac{1}{2}- \frac{1}{2k-1}, x(2k)=\frac{3}{2}+\frac{1}{2k}$, where $x(t)$ does not converge to $x^*$  
> **username_0**: And also we are in the non-linear case...  

---

## 2 answers

### Answer by username_2 on 2016-09-23. Score: 2 | Accepted answer

The OP correctly identified a mistake here. Since the author claims monotonicity for a general function, let's disprove it for the simple linear case.
Consider

$$x\_{t+1} = g(x\_t) = -0.5x\_t$$

This satisfies all the requirements and conditions stated by the author, and also that the derivative is smaller than unity in absolute values $\forall x$. But it converges with "damped oscillations", and so it is not monotonic since, say,

$$x\_0 = -3 < 0 = x^\*$$
$$x\_1 = 1.5$$
$$x\_2 = -0.75$$
etc

> **Comments:**
> **username_3**: I believe you meant damped oscillations (reduced over time) rather than dumped  
> **username_2**: @ThreeDiag Thanks for spotting this. Fixed.  

---

### Answer by username_4 on 2021-09-21. Score: 1

Since the OP asked for a rigorous proof, here is one.

By Acemoglu's inequality in the first part of his proof, we can separate $\{x(t)\}\_{t=0}^{\infty}$ into two subsequences, an increasing subsequence $\{x(t\_{i})\}\_{t\_{i}\in I}$ bounded above by $x^{\*}$ and a decreasing subsequence $\{x(t\_{j})\}\_{t\_{j} \notin I}$ bounded below by $x^{\*}$. Indeed, we define $I$ to be the set $\{t \in \mathbb{N} \mid x(t). By Acemoglu's inequality, $s>t$ implies $x(s)$ is strictly closer to $x^{\*}$ than $x(t)$ is. Thus, since $x(t\_{i}) for all $t\_{i} \in I$, $\{x(t\_{i})\}\_{t\_{i}\in I}$ is increasing. Similarly, $\{x(t\_{j})\}\_{t\_{j} \notin I}$ is decreasing and bounded below by $x^{\*}$

Assume that each of these subsequences is infinite. Then each converges to a limit, which we will denote by $y$ and $z$ respectively.

Note that it also follows from Acemoglu's inequality that $y=x^{\*}-\epsilon$ and $z=x^{\*}+\epsilon$ for some $\epsilon \geq 0$. Indeed, suppose that this is not the case (we will show this generates a contradiction). For convenience, assume $\vert y -x^{\*}\vert<\vert z-x^{\*}\vert$. Define
$$\delta:=\vert z-x^{\*}\vert-\vert y-x^{\*}\vert>0.$$
Since $\lim\_{i \to \infty}x(t\_{i})=y$, we can pick $t \in \mathbb{N}$ such that
$$\vert x(t)-y\vert<\frac{\delta}{2}.$$
The triangle inequality then tells us that
$$\vert x(t)-x^{\*}\vert <\vert y-x^{\*}\vert+\frac{\delta}{2}.$$
Now pick some $s \in \mathbb{N}$ such that $s >t$ and $x(s)>x^{\*}$ (such an $s$ exists by our assumption that both the constructed subsequences are infinite). Since $x(s)>z>x^{\*}$, we have that
$$\vert x(s)-x^{\*}\vert>\vert z-x^{\*}\vert.$$
Thus,
$$\vert x(t)-x^{\*}\vert <\vert y-x^{\*}\vert+\frac{\delta}{2}<\vert z-x^{\*}\vert <\vert x(s)-x^{\*}\vert.$$
But since $s>t$, this contradicts Acemoglu's inequality.

Now we will consider the value of $g(y)$. Since,
$$g(y)=g(\lim\_{i \to \infty}x(t\_{i}))=\lim\_{i \to \infty}g(x(t\_{i}))=\lim\_{i \to \infty}x(t\_{i}+1),$$
we must have that $g(y)=y$ or $g(y)=z$.

If $g(y)=z$, then we must have that $y=z=x^{\*}$ since if $y\neq x^{\*}$, we get a contradiction. Indeed, if $y \neq x^{\*}$, then Acemoglu's inequality implies that $g(y)$ is strictly closer to $x^{\*}$ than $y$ is; but $y$ and $z$ are equidistant from $x^{\*}$. Thus $g(y)=y$ and similarly $g(z)=z$. (If only one of the subsequences is infinite, we get this immediately.) But this implies that $y=z=x^{\*}$, as Acemoglu's inequality allows us to infer that if $y \neq x^{\*}$, then $g(y)$ is strictly closer to $x^{\*}$ than $y$ is.

> **Comments:**
> **username_5**: I'm not sure how you get to the claim that there are two monotone sequences whose limits are equally far from $x^\ast$. I think it would be good to be somwhat more specific where this comes from.  
> **username_4**: Thanks for the suggestion @tdm. I've updated the proof with more detail on that claim.  

---

