Prove that a sequence is increasing

Question

A city's population in the $n^{th}$ year is denoted by $x_n$ (in millions). If, $\forall n \in \mathbb N^+$, we have: $x_1 = \frac34$, $x_{n+1} = 2x_n - x_n^2$, show that as $n \to \infty$, the population will tend to a finite limit. What is this limit?

For this question, I am supposed to use the Monotone Convergence Theorem, so I decided to start off by showing that that sequence $(x_n)$ is bounded. I wrote:

For each $n \in \mathbb N^+$, $x_n \ge 0$ (population cannot be negative). Also, $x_{n+1} = x_n(2 - x_n)$. If $x_n > 2$ then $x_{n+1} < 0$ which is an impossibility. Therefore $0 \le x_n \le 2$ and so $(x_n)$ is bounded.

For the "monotone" part of the proof, I computed a couple of terms of the sequence and realised that it was increasing towards the value $1$. I tried induction but got stuck. Here's what I wrote:

Let $P(n)$ be the proposition that $x_n \le x_{n+1}$. $P(1)$ is true (not gonna show the working here). Assume that $P(k)$ is true for some $k \in \mathbb N^+$, i.e. $x_k \le x_{k+1}$. Then I need to show $x_{k+1} \le x_{k+2} = 2x_{k+1} - x_{k+1}^2$. We have $x_{k+1} = 2x_k - x_k^2 \le 2x_{k+1} - x_k^2$. But from the inductive hypothesis we get $x_k^2 \le x_{k+1}^2$, which means $2x_{k+1} - x_k^2 \ge 2x_{k+1} - x_{k+1}^2$ and so we can't conclude $x_{k+1} \le x_{k+2}$?

Any help in this question is appreciated.

Answer 1

Try this one instead: $x_{n+1}=2x_n-x_n^2=1-(1-x_n)^2$, so if $0<x_n<1$ then $0<x_{n+1}<1$, and we know $0<x_1<1$. Thus if you define $P(n)$ to be the proposition $0<x_n<1$, then $P(n)$ is true for all $n\in\mathbb{N}$.

Now, $x_{n+1}=2x_n-x_n^2>2x_n-x_n=x_n$ (as $0<x_n<1$ we have $0<x_n^2<x_n$). So $x_n$ is monotonically increasing, it is bounded and therefore $x=\lim x_n$ exists.

Take the limit $n\rightarrow+\infty$ in the equation $x_{n+1}=2x_n-x_n^2$ to get $$x=2x-x^2\implies x=0\textrm{ or }1$$ But $x$ cannot be $0$ since $x>x_1>0$.

Answer 2

$P(n)$ should be $0 \lt x_n \lt 1$. You should then be able to show that $P(n) \implies P(n+1)$ by plugging into the recurrence. As you say, $P(1)$ is easy to verify

Answer 3

First we show that $x_n<1$ for all $n$. By straight forward calculation we have $x_2=\frac{15}{16}$. Now assume $x_n<1$ for some $n$, then

$$x_{n+1}=2x_n-x_n^2\Rightarrow x_{n+1}-x_n=x_n-x_n^2=x_n(1-x_n)<1-x_n$$

which means $$x_{n+1}<1-x_n+x_n=1$$

thus we conclude that $x_n<1$ for all $n$.

Next we show that $x_n>0$ for all $n$ by induction. The base case is trivial, now suppose $x_n>0$ for some $n$, then since

$$x_{n+1}-x_n=x_n-x_n^2$$ and we have shown that $x_n<1$, thus $x_n-x_n^2>0$, so $x_{n+1}-x_n>0$

All in all $x_n\in(0,1)$ for all $n$. Also, from the proof we have shown that

$$x_{n+1}-x_n>0$$ for all $n$, so $x_n$ is increasing. Hence by monotone convergence theorem $\lim_{n\to\infty}x_n$ exists. And from the assumption

$$\lim_{n\to\infty}x_n=\lim_{n\to\infty}x_{n+1}=2\lim_{n\to\infty}x_n-(\lim_{n\to\infty}x_n)^2$$

Hence

$$\lim_{n\to\infty}x_n=1$$