I was looking at this article about a function $f(x) = \sqrt{x + \sqrt{x + \sqrt{x + ...}}} $.
The answer given in the article was $f(x) = \frac{1\pm\sqrt{1+4x}}{2}$ but another idea came up to my mind.
This can be solved using recurrence relation.
$$a_{i+1} = \sqrt{a_i + x}\,\, ,(a_0 = 0)$$
$$f(x) = \lim_{i \to \infty} a_i$$
But I also wondered what the general solution of this recurrence relation. I searched for this issue for hours, but only thing I could find was the solution when $a_i$ is to the first power (degree $1$). Logistic map was also found which is a recurrence relation of degree $2$. The equation can be rewritten as $a_{i+1}^2 = a_i + x$ so I thought I could draw something out of this. But the logistic map seems to have a solution only for $r=4$.
How do I solve this recurrence relation?
EDIT 12/18/2017
Thanks for openspace's answer. Here's my solution. This might contains some mistakes in wording since I didn't get math education in English. I'd appreciate it if somebody corrected them if any.
For $x=0\,$, $a_1 = \sqrt{a_0 + x} = \sqrt{0+0} = 0$ so $a_n = 0$ for any $n$.
For $x<0\,$, $\lim_{i \to \infty} a_i$ is not real for $a_i$ is not real for $i>0$. I prove it here.
In this section $a_j$ is used instead of $a_i$ since $i$ can be confused for an imaginary unit $i$.
if $a_j$ is a complex number, it can be written as $p_j + iq_j$ where $p_j$ and $q_j$ are real. So the following is true.
$$a_{j+1} = p_{j+1} + iq_{j+1} = \sqrt{a_j + x} = \sqrt{p_j + x + iq_j}$$
So,
$$ p_{j+1} + iq_{j+1} = \sqrt{p_j + x + iq_j} \\ \Rightarrow (p_{j+1} + iq_{j+1})^2 = \sqrt{p_j + x + iq_j} \\ \Leftrightarrow p_{j+1}^2 - q_{j+1}^2 + 2ip_{j+1}q_{j+1} = p_j + x + iq_j$$
By comparing the real and imaginary parts, I get the following.
$$ p_{j+1} = \pm \sqrt{\frac{(p_j + x) + \sqrt{(p_j + x)^2 + q_j^2}}{2}} \\ q_{j+1} = \pm \sqrt{\frac{-(p_j + x) + \sqrt{(p_j + x)^2 + q_j^2}}{2}} $$
$a_{j+1}$ being real is equivalent to $q_{j+1} = 0$
$$q_{j+1} = 0 \\ \Leftrightarrow \pm \sqrt{\frac{-(p_j + x) \pm\sqrt{(p_j + x)^2 + q_j^2}}{2}} = 0 \\ \Leftrightarrow -(p_j + x) \pm\sqrt{(p_j + x)^2 + q_j^2} = 0 \\ \Rightarrow q_j = 0 \\$$
Its contraposition is below.
$$q_j \neq 0 \Rightarrow q_{j+1} \neq 0$$
Using this relation recursively yields the following.
$$q_1 \neq 0 \Rightarrow q_j \neq 0$$
However, $a_1$ is below.
$$a_1 = \sqrt{a_0 + x} = \sqrt{0+x} = i\sqrt{|x|} \,(x<0) \\ \Leftrightarrow q_1 \neq 0 \\ \Rightarrow q_j \neq 0$$
Thus, For $x<0\,$, $\lim_{i \to \infty} a_i$ is not real for $a_i$ is not real for $i>0$.
For $x>0\,$ I prove the sequence is bounded and increasing.
I introduce a function here.
$$g(y) = \sqrt{y + x}$$
The solution of $g(y) = y\,$ is $\,y = \frac{1 \pm\sqrt{1 + 4x}}{2}\,$ which is real since $x>0 \Leftrightarrow 1+4x>0$.Since $g(y)>0 \Leftrightarrow y>0$ and $1-\sqrt{1+4x} < 0 \Leftrightarrow x>0$ which is true, $\,y = \frac{1 + \sqrt{1 + 4x}}{2}\,$. From now on, I call this $y$ $Y$.
Here, I prove $a_i$ is upper-bounded.
$$Y > a_i \Leftrightarrow Y + x > a_i +x > 0 \,(a_i>=0, x>0)\\ \Leftrightarrow \sqrt{Y+x} > \sqrt{a_i+x} \Leftrightarrow Y > a_{i+1}$$
Since $a_0 = 0 < Y = \frac{1 + \sqrt{1 + 4x}}{2}$ because $x>0$, this is true. $a_i$ is upper-bounded.
Next, when $a_i < Y$, the following is true.
$$a_{i+1}>a_i \Leftrightarrow \sqrt{a_i + x}>a_i \\ \Leftrightarrow a_i + x > a_i^2$$
It's trivial that both sides of the equation are positive since $x>0 and a_0=0$.
$$ a_i + x > a_i^2 \Leftrightarrow Y^2 + (a_i + x) > (Y + x) + a_i^2 \,(Y=\sqrt{Y+x}) \\ \Leftrightarrow (Y-a_i)(Y+a_i) > Y - a_i \\ Y + a_i > 0 \,(Y - a_i>0 \Leftrightarrow Y> a_i)$$
This is true since $Y>0$ and $a_i>=0$ thus $a_i$ is increasing.
Since $a_i$ is upper-bounded and increasing, $a_i$ has a limit. For a sufficiently large $i$, $a_i$ is $Y$. The act of proving was finished.
But I noticed one thing. The original answer is real for $x>1/4$ but mine is real for $x>=0$. Moreover, the original has two solution while mine has one. Where did I go wrong? There are two thing.
- The original answer is wrong in some points
$f(x)$ is obviously not negative so it should be like this.
$$ f(x) = \frac{1+\sqrt{1+4x}}{2} for x>0 \\ f(x) = \frac{1\pm\sqrt{1+4x}}{2} for 0>=x>=-1/4 \\ f(x) has no real solution for x<-1/4$$
- The ultimate value depends on the start value $a_0$
If $a_0$ is sufficiently large, the ultimate value of the sequence is thought to converge to $\frac{1+\sqrt{1+4x}}{2} for 0>=x>=-1/4$. Draw graphs of $z=\sqrt{y+x}$ and $z=y$ on a y-z plane and consider $y$ and $z$ as $a_i$ and $a_{i+1}$. Just see how the points of the sequence "hops" from one line to another. You could see the points go toward the larger one of the cross points of two graph. When $x=-1/4$, the two graph only contacts at one point. The content of the square root is zero. That's the only solution.
- my solution is a sequence, which goes only "one direction."
A sequence converges to only one point if it does. As I said earlier, the points of the sequence on a y-z plane only goes toward one of the solutions. But The "reverse" sequence $a_{i} = \sqrt{a_i + x}$ would give the opposite result.
I'm still curious about the behavior of $a_i$ when $x<0$. Will the sequence converge to certain points, which probably is $\frac{1 \pm\sqrt{1 + 4x}}{2}$? But the calculation is quite tough to chew. As written above, getting the real and imaginary parts of $a_{i+1}$ from $a_i$ is pretty messy. I also tried for polar coordinates but didn't make it. I'll try some computer simulation for this.
First of all. You need to show that sequence is bounded. And it's increasing, so it has a limit.
Then for sufficient large $n$ : $a_{n+1}$~$a_{n}$. So $a_{n}^{2} = a_{n}+x$.
Now solve this equation and you will get the necessary.