How to prove that $x_{n+1}=\sqrt[k]{a+x_n}$ is bounded above?

Question

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!

Answer 1

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.

Answer 2

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$$

Answer 3

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$.

Answer 4

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$.

Answer 5

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$.