Prove that the sequence is bounded above.

Question

I have proved that the induction hypothesis is true for n=1. However when trying to prove that the hypothesis is true for n=k+1 when we assume that it is true for n=k, I am getting stuck. I have tried various manipulations to prove that the hypothesis is true for n=k+1. Kindly help.

Answer 1

1. $a_n\in\left[0,\sqrt{x}\right]$.

Initially, $a_0=0\in\left[0,\sqrt{x}\right]$.

Inductively, suppose $a_k\in\left[0,\sqrt{x}\right]$. We need to show $a_{k+1}\in\left[0,\sqrt{x}\right]$. We have $$ a_{k+1}=a_k+\frac{1}{2}\left(x-a_k^2\right)=-\frac{1}{2}a_k^2+a_k+\frac{x}{2}. $$ Note that the right-hand side can be regarded as a quadratic function of $a_k$, whose global maximal point is $a_{k*}=1$. Provided that $a_k\in\left[0,\sqrt{x}\right]\subseteq\left[0,1\right]$, it is clear that

• the maximal value of the right-hand side $-a_k^2/2+a_k+x/2$ is obtained at $a_{k*}=\sqrt{x}$, which gives $$ -\frac{1}{2}a_{k*}^2+a_{k*}+\frac{x}{2}=-\frac{x}{2}+\sqrt{x}+\frac{x}{2}=\sqrt{x}. $$
• the minimal value of the right-hand side $-a_k^2/2+a_k+x/2$ is obtained at $a_{k**}=0$, which gives $$ -\frac{1}{2}a_{k**}^2+a_{k**}+\frac{x}{2}=0+0+\frac{x}{2}=\frac{x}{2}\ge 0. $$

Therefore, $a_{k+1}=-a_k^2/2+a_k+x/2\in\left[0,\sqrt{x}\right]$, as is expected.

To sum up, it suffices to conclude that $a_n\le\sqrt{x}$ for all $n\ge 0$.

2. $a_{n+1}\ge a_n$.

This step does not need to use mathematical induction. Provided that $a_n\in\left[0,\sqrt{x}\right]$, it is straightforward that $a_n^2\in\left[0,x\right]$. Thanks to $a_n^2\le x$, $$ a_{n+1}=a_n+\frac{1}{2}\left(x-a_n^2\right)\ge a_n+\frac{1}{2}\left(x-x\right)=a_n. $$ Therefore, $a_n$ is always non-decreasing.

3. $a_n\to\sqrt{x}$.

Combine the above two steps, and the monotone convergence theorem implies that $a_n$ converges, denoted by $a_n\to y$. We need to show $y=\sqrt{x}$. Note that it makes sense to take the limit on both sides of $$ a_{n+1}=a_n+\frac{1}{2}\left(x-a_n^2\right), $$ which gives $$ y=y+\frac{1}{2}\left(x-y^2\right). $$ Solve this quadratic equation with respect to $y$ under the constraint $y\in\left[0,\sqrt{x}\right]$, and it follows immediately that $y=\sqrt{x}$, as is expected.

Answer 2

Here is a different proof:

Let $f(a) = a+{1\over 2}(x-a^2)$. Note that $f(0) = {1 \over 2} x$, $f'(a) = 1-a$ and $f(a) \le f(1) = {1 \over 2} (1+x) \in (0,1)$ for all $a$. Note that $f'(a) \ge 0$ for all $a \le 1$.

In particular, if $a_{n+1} = f(a_n)$, with $a_n = 0$, we see that $a_n \le f(1)$ and $a_{n+1} \ge a_n$. Hence $a_n \to a$ for some $a$ and so $f(a) = a$, or equivalently, $a = \sqrt{x}$.