How to prove that $x_{n+1}=\sqrt[k]{a+x_n}$ is bounded above? Let $k\in\mathbb N$ with $k\ge2$ and fix $a>0$. Let $x_1=\sqrt[k]{a}$ and $x_{n+1}=\sqrt[k]{a+x_n}$. I want to prove that this sequence is bounded above.
My proof is by induction. Suppose that $L>0$ be such that $L^k=L+a$. If $n=1$, then $x_1=\sqrt[k]{a}\le L$, since $a\le a+L$. So if $x_n\le L$, then we have
$$x_{n+1}^k=x_n+a\le L+a=L^k$$
and so $x_{n+1}\le L$.
But I don't know how to justify if such a $L$ exists. So I think maybe there is some better ways. So my main question is, 
What other methods can we use to prove that $\{x_n\}$ is bounded above? Thanks!
 A: Since we actually just need $L+a\le L^k$ in your induction we could find an explicit $L$ depending on $a$ :


*

*If $0 \lt a \le 2$ then choose $L=2$ so we have 
$$a+L \le 4 \le 2^k = L^k$$

*If $ 2 \le a$ then choose $L=a$ so that
$$ a + L = 2a \le a^2 \le a^k = L^k$$
since $k \ge 2$.

A: Your proof is actually very well put!
To prove the existence of $L>0$ such that $L^k-L=a$ just consider $f:x\mapsto x^k-x$, it is continuous, $f(0)=0$ and $\lim_{x\to \infty}f(x) = \infty$. Then, using the theorem of intermediate values: $$\forall a>0, \exists L>0,f(L)=L^k-L=a$$
A: Technically, this will not answer your question, but it will allow you to prove that there exists $L > 0$ such that $L^k=L+a$. 
Let $g : \mathbb{R} \rightarrow \mathbb{R}$ be given by
$$g(x) = x^k - x - a.$$
Then $g$ is continuous, $g(0) < 0$, and $$g(x) \rightarrow \infty, \quad x\rightarrow \infty, \quad x \in \mathbb{R}.$$
Here it is important that $k > 1$. In particular, $g$ assumes both positive and negative values on the positive real line. It follows that $g$ as at least one zero $L > 0$.
A: Let's say that we want to prove $|x_n|\leq L$ for all $n\in\mathbb N$. We would like to prove it by induction, since your sequence is given recursively. But, here's the thing, we don't know what $L$ we should choose yet, so we will try to go through the inductive proof first and see what $L$ will allow us to get through it.
Assume that we have $|x_n|\leq L$ and we want to prove that it implies $|x_{n+1}| \leq L$. We have
$$|x_{n+1}|\leq L \iff |x_{n+1}|^k\leq L^k \iff |x_n + a| \leq L^k$$
and the question is what can we use to prove $|x_n+a|\leq L^k$. We know that $|x_n|\leq L$, so one should think of triangle inequality: $|x_n + a|\leq |x_n|+|a|\leq L + |a|$. Now we see that it is sufficient to find $L$ such that $$L + |a| \leq L^k.\tag{1}$$ We also need to have $|x_1| = |\sqrt[k]a| \leq L$, so we might want to try $L = |\sqrt[k]a|$ in $(1)$. Unfortunately, it doesn't work. The next obvious thing to try is $L = |a|$. In that case $(1)$ becomes $$|a|+|a| \leq |a|^k \iff |a|^{k-1} \geq 2.$$ Ah, so now we know that $L = |a|$ works for $|a| \geq 2$ (this is a crude estimate, but we don't really want to depend on $k$). And what about $|a|< 2$? Since $2$ seems to be the magical number here, why don't we try $L = 2$:
$$2+|a| < 2 + 2 \leq 2^k,\ k\geq 2.$$
Great, it works.
Finally, we see that $L = \max\{|a|,2\}$ will do the job and let us prove the boundedness by induction.
Hopefully, this sheds some light onto how someone can stumble upon seemingly unmotivated bounds in analysis.
A: To find the positive root of
$f(x)
=x^k-x-a$
where $a > 0$,
note that
$f(0) = -a$,
$f(1) = -a$,
and,
by Bernoulli's inequality,
$f(1+a)
\ge 1+ka-1-a-a
=a(k-2)
\ge 0$
since
$k \ge 2$.
Therefore $f$ has a root
between $1$ and $1+a$.
Also,
$f'(x)
=kx^{k-1}-1
\gt 0$
for $x \ge 1$
so $f$ has at most one root
for $x \ge 1$.
Therefore
$f$ has exactly one root
for $x \ge 1$
and that root is in
$[1, 1+a]$.
Call this root
$x_a$.
Also,
$f''(x) = k(k-1)x^{k-2}
\gt 0$
for
$x > 0$
so
$f'(x)$ is increasing for
$x > 0$.
Since
$f'(1) = k$,
$f'(x) \gt k$
for $x \gt 1$.
Let's do a Newton
and find a better approximation
to that root.
This actually is not needed,
but I like doing it.
Newton's iteration is
$\begin{array}\\
x-\dfrac{f(x)}{f'(x)}
&=x-\dfrac{x^k-x-a}{kx^{k-1}-1}\\
&=\dfrac{x(kx^{k-1}-1)-(x^k-x-a)}{kx^{k-1}-1}\\
&=\dfrac{kx^{k}-x-x^k+x+a}{kx^{k-1}-1}\\
&=\dfrac{(k-1)x^{k}+a}{kx^{k-1}-1}\\
\end{array}
$
For $x=1$ this is
$\dfrac{(k-1)+a}{k-1}
=1+\dfrac{a}{k-1}
$.
By Bernoulli, again,
$f(1+\frac{a}{k-1})
=(1+\frac{a}{k-1})^k-(1+\frac{a}{k-1})-a
\ge 1+k\frac{a}{k-1}-(1+\frac{a}{k-1})-a
= 0
$,
so the root is in
$[1, 1+\frac{a}{k-1}]$.
Back to the
relevant stuff.
Since
$f'(x_a) > 0$,
if
$x > x_a$
then
$f(x) > 0$
so
$x^k > x+a$
or
$x > \sqrt[k]{x+a}$.
Therefore the iteration
$x_{n+1}
=\sqrt[k]{x_n+a}
$
decreases if
$x_n > x_a$.
Also,
if
$x_{n+1} < x_a$
then
$\sqrt[k]{x_n+a}
\lt x_a
$
or
$x_n+a < x_a^k
=x_a+a$
(since
$x_a^k-x_a-a=0$)
or
$x_n < x_a$,
which contradicts the assumption that
$x_n > x_a$.
Therefore,
$x_n > x_a$
implies that
$x_a < x_{n+1} < x_n$,
so the iterations
decrease and are
bounded below by $x_a$.
Similarly,
if
$1 < x_n < x_a$
then
the iterations
increase and are
bounded above by $x_a$.
I will leave to you
the proof that
the iterations
actually converge to $x_a$.
Hint:
$f'(x) > 0$
for $x \ge 1$.
