Since I was having some issues with the mathy math of this problem, I thought I'd post it to see what other cool peeps had to say about it as well.
let $x_1 =0$ and define $x_{n+1} = \frac{( x_n^2 + 1)}{2}$.
(a) Prove that $x_{n+1} -x_n > 0$ for all $n$.
(b) Prove that $x_n < 1$ for all $n$.
(c) Deduce that the sequence converges and find the limit.
Any ideas?
I think you may have typed the formula incorrectly; it should be $x_1 = 0$ and $x_{n+1} = (x_n^2+1)/2$. Given this, this is what I played with for part a:
For $n=2$, $x_2 = 1/2$, so
$$x_2 - x_1 = \frac{1}{2} - 0 >0.$$
For induction, suppose $x_{n+1} - x_n >0.$ Then,
$$
x_{n+2} - x_{n+1} = \frac{x_{n+1}^2 +1}{2} - \frac{x_{n}^2 + 1}{2} = \frac{1}{2} \left( x_{n+1}^2 + 1 - x_n^2 - 1 \right)
$$
$$
= \frac{1}{2} \left(x_{n+1}^2 - x_n^2 \right) = \frac{1}{2} (x_{n+1} + x_n)(x_{n+1}-x_n)>0,
$$
since both $x_{n+1}$ and $x_n$ are manifestly positive, and $(x_{n+1} - x_n)>0$ is assumed.
@Cromer
are you sure we can say $x_{n+2} = \displaystyle\frac{x_{n+1}^2 + 1}{2}$??
Yes; this is just applying our recursion formula $x_{n+1} = (x_n^2+1)/2$, but replacing $n$ with $n+1$.
For parts b and c:
b.) Since we proved in part a that $x_{n+1} - x_n > 0$ we can use that here.
Suppose $x_{n+1} - x_n > 0$
$$\begin{array}{lcl}\displaystyle\frac{\left(x_n^2+1\right)}{2} - x_n & > & 0\\
\displaystyle\frac{\left(x_n^2+1\right)}{2} - \frac{2x_n}{2} & > & 0\\
\displaystyle\frac{\left(x_n^2-2x_n+1\right)}{2} & >& 0\\
\displaystyle\frac{\left(x_n-1\right)^2}{2} & > & 0\\
(x_n-1)^2 & > & 0\\
\pm (x_n-1) & > & 0\\
-x_n +1 & > & 0\end{array}$$
Which implies $x_n < 1$.$\blacksquare$
c.) Deduce that the sequence converges and find the limit.
I think we can assume that this converges because of the monotone convergence theorem. (I think?? Please let me know if that's no bueno.)
Assume that $x=\displaystyle\lim_{n\rightarrow\infty} x_{n+1} = \lim_{n\rightarrow\infty}x_n$
$$\begin{array}{rcl}x & = & \displaystyle\frac{x^2+ 1}{2}\\
2x & = & x^2 + 1\\
0 & = & x^2 - 2x + 1\\
0 & = & (x-1)^2\\
0 & = & \pm(x-1)\end{array}$$
Therefore $x = 1$.
I showed a lot more computational steps than necessary but that was just because I wanted to make sure it was clear.
@qkhan
For part c, you CAN assume that the series converges.
However, part b feels a bit hand wavy due to the fact that you are forced to drop a sign towards the end. Instead, lets try to prove it from $x_{n+1}-1 <0$
First we prove our base case,
$x_1=0<1$
Okay that part was easy.
Now assuming $x_n<1$ lets prove $x_{n+1}<1$ starting with $x_{n+1}-1 <0$
$$x_{n+1}-1=\frac{x_n^2+1}{2}-1=\frac{x_n^2+1-2}{2}=\frac{x_n^2-1}{2} $$
Now comes the "thinky think" part. We have assumed $x_n<1$. So, $x_n^2$ is surely less than 1. This sequence is monotone increasing starting from zero so, specifically, $0\leq x_n^2<1$. Now a number in this range minus 1 MUST be negative so dividing this number by two must also be negative. Therefore, $$x_{n+1}-1<0$$ which implies that $$x_{n+1}<1$$
My version is a bit wordy but so are all my other proofs.
I just left off the last step because I thought it might've been unnecessary but just to clarify what I did was:
$-x_n + 1 > 0$
$-x_n > -1$
And then multiplied through by -1 so the sign flipped to get $x_n < 1$
But I see what you're saying! I wasn't sure if this method was viable but it got the answer okay so I just went with it. Yours seem actually legit and way more reasonable so thank you for sharing, @sfrye.