I was trying to solve a statistics problem on expected values when the following recurrence relation came up.
Quite frankly I'm stumped on how to solve it ... even to the point that I'm starting to believe that it has no possible solutions.
$X_{n}=\frac{1}{2}*(1+X_{n-1}^2)$ for $X_{0} = 0.5$ (tends to 1)
(I've already taken a look at How to solve quadratic recurrence relation which would only prove helpful if my recurrence has no closed form solutions in which case I would appreciate a proof)
If you run the following code in MATLAB, the random sampling and the original function do not completely match (at each step you run max(H(i-1), rand(0,1)):
G = 0.5; for t=2:100; G(t) = 0.5+0.5*G(t-1)^2; end;
H = rand(1,100000); for i=2:100; H(i,1:100000)=max(H(i-1,1:100000),rand(1,100000)); endfor; plot(mean(H')); hold on; plot(G,'g'); hold off
A closed form for $X_n$ is unlikely, but to rigorously show that $$ \lim_{n\to\infty}X_n=1 $$ we can argue as follows . . .
It's clear that $X_n > 0$ for all $n$.
Also we have $X_0 < 1$, and if $X_{n-1} < 1$ then $$ X_n = \frac {1+X_{n-1}^2}{2} < \frac {1+1^2}{2} = 1 $$ so $X_n < 1$ for all $n$.
Then we get \begin{align*} X_n-X_{n-1} &= \frac {1+X_{n-1}^2}{2} - X_{n-1} \\[4pt] &= \frac {1-2X_{n-1}+X_{n-1}^2}{2} \\[4pt] &= \frac {(1-X_{n-1})^2}{2} \\[4pt] & > 0 \\[4pt] \end{align*} so the sequence $X_0,X_1,X_2,...$ is monotonically increasing, hence, since the sequence is bounded above, it follows that it approaches a limit, $L$ say, as $n$ approaches infinity.
Then from the recursion $$ X_n = \frac {1+X_{n-1}^2}{2} $$ we get \begin{align*} & L = \frac {1+L^2}{2} \\[4pt] \implies\;& 1-2L+L^2=0 \\[4pt] \implies\;& (1-L)^2=0 \\[4pt] \implies\;& L=1 \\[4pt] \end{align*}