Maths Olympiad Prep

Library / /19 of 82

Algebra Difficulty 5.1 AIME, harder Prove it Croatia

Prove that for every positive integer nn
n+(n1)+(n2)++2+1<n+1. \sqrt{n + \sqrt{(n-1) + \sqrt{(n-2) + \dots + \sqrt{2 + \sqrt{1}}}}} < \sqrt{n} + 1.

Solution

Let Sn=n+(n1)+(n2)++2+1S_n = \sqrt{n + \sqrt{(n-1) + \sqrt{(n-2) + \dots + \sqrt{2 + \sqrt{1}}}}}.

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

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

Inductive step:
Assume Sn1<n1+1S_{n-1} < \sqrt{n-1} + 1.
Consider Sn=n+Sn1S_n = \sqrt{n + S_{n-1}}.

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

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

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

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.