Mathematica competitions in Croatia

Let $S_n=\sqrt{n+\sqrt{(n-1)+\sqrt{(n-2)+\cdots +\sqrt{2+\sqrt{1}}}}}$.

We will prove by induction on $n$ that $S_n<\sqrt{n}+1$ for all positive integers $n$.

Base case ($n=1$): $S_1=\sqrt{1}=1<\sqrt{1}+1=2$.

Inductive step: Assume $S_{n-1}<\sqrt{n-1}+1$. Consider $S_n=\sqrt{n+S_{n-1}}$.

We want to show: $$\sqrt{n+S_{n-1}}<\sqrt{n}+1.$$

It suffices to show that $n+S_{n-1}<(\sqrt{n}+1{)}^2=n+2\sqrt{n}+1$. Subtract $n$ from both sides: $$S_{n-1}<2\sqrt{n}+1.$$

But by the induction hypothesis, $S_{n-1}<\sqrt{n-1}+1$. So it is enough to show: $$\sqrt{n-1}+1<2\sqrt{n}+1$$ which is equivalent to $\sqrt{n-1}<2\sqrt{n}$, which is true for all $n\ge 1$.

Therefore, by induction, $S_n<\sqrt{n}+1$ for all positive integers $n$.