I saw this on quora:
Use induction to show that $\sqrt{1^2+\sqrt{2^2+\sqrt{3^2 ...+\sqrt{(n-1)^2+\sqrt{n^2}}}}} \le 2 $.
My question is simpler.
If $x_n =\sqrt{1^2+\sqrt{2^2+\sqrt{3^2 ...+\sqrt{(n-1)^2+\sqrt{n^2}}}}} $, how can $x_{n+1}$ be expressed in terms of $x_n$?
No ellipsis ("...") or iterations are allowed.
This is all I've come up with, but it doesn't seem to be of much use.
Let
$\begin{array}\\ f_{n}(x) &=\sqrt{1^2+\sqrt{2^2+\sqrt{3^2 ...+\sqrt{n^2+x}}}}\\ f_{n+1}(x) &=\sqrt{1^2+\sqrt{2^2+\sqrt{3^2 ...+\sqrt{n^2+\sqrt{(n+1)^2+x}}}}}\\ &=f_n(\sqrt{(n+1)^2+x})\\ \end{array} $
so if $y =\sqrt{(n+1)^2+x} $, $f_n(y) =f_{n+1}(x) $. $y^2 =(n+1)^2+x $, so $x =y^2-(n+1)^2 $ or $f_{n+1}(y^2-(n+1)^2) =f_n(y) $.
[Not intended as a complete answer. It doesn't relate $x_n$ and $x_{n+1}$ as requested by OP, in part because that's not the "right" thing to look at.]
It is often harder to deal with inserting the variable just at the very extreme end of the nested roots. This makes intuitive sense in part because the function is so un-sensitive to changing just that value. E.g. I expect that $f_n (2^{2^n}) - f_n (0) < 1 $ (but am not fully certain).
It is generally more useful to define the recursive nature by "shifting" the terms, which can be done in the following way:
Let $g_n(x) = \sqrt{ (x+1)^2 + \sqrt{ (x+2)^2 + \sqrt{ \ldots + \sqrt{ (x+n)^2 }}}}$
Then, $ g_{n} (x) = \sqrt{ (x+1)^2 + g_{n-1}(x+1)}$.
We are asked to show that $g_n(0) \leq 2$.
Why is this possibly the "right" thing to look at?
One naive/obvious/intuitive/brute-force approach is to "square both sides, subtract terms, and repeat till we get everything". In the language of this notation, we can write it as:
WTS $g_n(0) \leq 2 $
$\Leftarrow g_{n-1} (1) \leq 2^2 - 1^2 = 3 $
$\Leftarrow g_{n-2} (2) \leq 3^2 - 2^2 = 5 $
$\Leftarrow g_{n-3} (3) \leq 5^2 - 3^2 = 16 $
$\Leftarrow g_{n-4} (4) \leq 16^2 - 4^2 = 240 $
$\Leftarrow \vdots $
$ \Leftarrow g_1 (n-1) \leq $ ??
Now, $g_1 (n-1) = n$, and it is clear that the RHS is huge (almost squaring each time), so the last inequality should almost always be true, especially in a hand-waving context.
Rigorizing this simply requires finding a good bound on the RHS. By staring and conjecturing really hard, one might come up with:
$g_1 (n-1) < n+1 $
$\Rightarrow g_2 (n-2) < \sqrt{ (n-1)^2 + n+1} < n$ for $n-2 \geq 0$
$\Rightarrow g_3 (n-3) < \sqrt{ (n-2)^2 + n} < n-1$ for $n-3 \geq 0$
$\Rightarrow \vdots $
$\Rightarrow g_{n-1} (1) < \sqrt{ 2^2 + 4} < 3$
$\Rightarrow g_n(0) < \sqrt{1^2 + 3 } = 2 $.
Note: It's somewhat surprising that we have a linear bound (though that makes the math nice). There are other possibilities that make use of the exponential growth.
To proceed by induction, one would have to guess that the strengthened hypothesis is
This can be easily proven by inducting on $n$, and is essentially that reversed chain
The base case is $ g_1 (m) = m+1 < m+2 $.
The induction step is $ g_{n+1} (m) = \sqrt{ (m+1)^2 + g_n(m+1) } < \sqrt{(m+1)^2 + m+3 } < m+2. $
Hence $g_n(0) < 2 $.
There could be other ways to prove the problem by induction. For example, another strengthened induction approach would be to show that $ x_n < 2 - h(n)$, in which case we want to show that $x_{n+1} - x_n < h(n) - h(n+1) $.
This might be why studying how $x_{n+1}$ is related to $x_n$ could be helpful. However, as explained earlier, it's very hard to get a handle on this difference, because of how nested everything is.