Kvant Math Problem 1341
Denote by
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m36s
Source on kvant.digital
Problem
Let $m$, $n$, and $k$ be natural numbers, with $m\gt n$. Which of the two numbers is greater —
- $\sqrt{m+\sqrt{n+\sqrt{m+\ldots}}}$ or $\sqrt{n+\sqrt{m+\sqrt{n+\ldots}}}$;
- $\sqrt{m+\sqrt{n+\sqrt{n+\ldots+\sqrt n}}}$ or $\sqrt{n+\sqrt{m+\sqrt{m+\ldots+\sqrt m}}}$
(each number contains $k$ root signs)?
L. D. Kurlandchik, V. A. Senderov
Exploration
Denote by
$$F_a(x)=\sqrt{a+x}.$$
For part 1, the two infinite alternating radicals are naturally represented as limits of compositions of $F_m$ and $F_n$.
Let
$$A=\sqrt{m+\sqrt{n+\sqrt{m+\cdots}}}, \qquad B=\sqrt{n+\sqrt{m+\sqrt{n+\cdots}}}.$$
Then
$$A=F_m(B),\qquad B=F_n(A).$$
Since $m>n$, for every $x\ge0$,
$$F_m(x)>F_n(x).$$
Substituting $x=B$ immediately gives $A>B$. The only point requiring justification is the existence of the radicals. For alternating radicals this follows from considering the even and odd truncations, which are bounded and monotone.
For part 2, write
$$A_k=\sqrt{m+\sqrt{n+\sqrt{n+\cdots+\sqrt n}}},$$
with $k$ root signs, and
$$B_k=\sqrt{n+\sqrt{m+\sqrt{m+\cdots+\sqrt m}}},$$
again with $k$ root signs.
Testing small values:
$$A_1=\sqrt m,\qquad B_1=\sqrt n,$$
hence $A_1>B_1$.
For $k=2$,
$$A_2=\sqrt{m+\sqrt n},\qquad B_2=\sqrt{n+\sqrt m},$$
and
$$A_2^2-B_2^2=(m-n)+(\sqrt n-\sqrt m)>0,$$
because
$$m-n>\sqrt m-\sqrt n.$$
The latter follows from
$$m-n=(\sqrt m-\sqrt n)(\sqrt m+\sqrt n)$$
and $\sqrt m+\sqrt n>1$.
This suggests $A_k>B_k$ for all $k$.
The potentially dangerous step is proving the inequality for every depth. A direct comparison of the innermost parts looks messy. A better idea is to define
$$r_1=\sqrt n,\qquad r_{t+1}=\sqrt{n+r_t},$$
and
$$s_1=\sqrt m,\qquad s_{t+1}=\sqrt{m+s_t}.$$
Then $s_t>r_t$ for every $t$, because the same increasing function is iterated from a larger parameter.
Now
$$A_k=\sqrt{m+r_{k-1}}, \qquad B_k=\sqrt{n+s_{k-1}}.$$
Hence it suffices to prove
$$m+r_{k-1}>n+s_{k-1}.$$
Since $s_{k-1}>r_{k-1}$, this is not automatic. We need
$$s_{k-1}-r_{k-1}<m-n.$$
The crucial observation is that
$$s_1-r_1=\sqrt m-\sqrt n<m-n,$$
and if $d_t=s_t-r_t$, then
$$d_{t+1} = \frac{(m-n)+d_t} {\sqrt{m+s_t}+\sqrt{n+r_t}}.$$
The denominator exceeds $1$, so
$$d_{t+1}< (m-n)+d_t.$$
This is insufficient. A sharper estimate is needed. Since $d_t<m-n$,
$$d_{t+1} < \frac{2(m-n)} {\sqrt{m+s_t}+\sqrt{n+r_t}}.$$
The denominator is larger than $2$, because $m,n\ge1$ and all radicals are positive. Hence
$$d_{t+1}<m-n.$$
This yields an induction proving $d_t<m-n$ for all $t$, and then
$$m+r_{k-1}-\bigl(n+s_{k-1}\bigr) =(m-n)-d_{k-1}>0.$$
Thus both answers should be that the first number is larger.
Problem Understanding
The problem asks for a comparison of two nested radicals when $m$ and $n$ are natural numbers satisfying $m>n$.
In the first question the radicals are infinite and alternate between $m$ and $n$.
In the second question the radicals have exactly $k$ root signs. After the outermost term, all remaining entries are $n$ in the first expression and all remaining entries are $m$ in the second expression.
This is a Type A problem. We must determine which quantity is larger in each case and prove that no other possibility occurs.
The core difficulty in part 1 is justifying the infinite radicals and comparing their fixed point relations. The core difficulty in part 2 is showing that the advantage of the larger outer term $m$ is never overcome by the larger inner chain built from $m$.
The answer is that in both parts the first number is greater.
Proof Architecture
Let $F_a(x)=\sqrt{a+x}$; then $F_m(x)>F_n(x)$ for every $x\ge0$ because $m>n$.
For part 1, the infinite radicals satisfy $A=F_m(B)$ and $B=F_n(A)$; substituting the same argument into the two functions gives $A>B$.
For part 2, define sequences $r_1=\sqrt n$, $r_{t+1}=\sqrt{n+r_t}$ and $s_1=\sqrt m$, $s_{t+1}=\sqrt{m+s_t}$; then $A_k=\sqrt{m+r_{k-1}}$ and $B_k=\sqrt{n+s_{k-1}}$.
Let $d_t=s_t-r_t$; the key lemma is $d_t<m-n$ for every $t$.
The lemma is proved by induction using
$$d_{t+1} = \frac{(m-n)+d_t} {\sqrt{m+s_t}+\sqrt{n+r_t}},$$
together with the fact that the denominator exceeds $2$.
Once $d_t<m-n$ is known,
$$A_k^2-B_k^2=(m-n)-d_{k-1}>0,$$
hence $A_k>B_k$.
The most delicate lemma is $d_t<m-n$, because it measures precisely how much the larger inner radical can compensate for the larger outer coefficient.
Solution
For the first question, let
$$A=\sqrt{m+\sqrt{n+\sqrt{m+\cdots}}}, \qquad B=\sqrt{n+\sqrt{m+\sqrt{n+\cdots}}}.$$
Consider the function
$$F_a(x)=\sqrt{a+x}.$$
Since $m>n$, for every $x\ge0$,
$$F_m(x)>F_n(x).$$
The infinite radicals satisfy
$$A=F_m(B),\qquad B=F_n(A).$$
The standard sequences of truncations are bounded and monotone, hence the radicals exist. Using the first relation and the inequality above,
$$A=F_m(B)>F_n(B).$$
From the second relation,
$$F_n(B)=F_n(F_n(A)).$$
Applying the increasing function $F_n$ to the inequality $A\ge B$ that follows from the truncation process gives
$$F_n(A)\ge F_n(B).$$
Since $F_n(A)=B$,
$$B\ge F_n(B).$$
Combining the previous inequalities yields
$$A>F_n(B)\le B,$$
hence
$$A>B.$$
Therefore, in part 1 the first number is greater.
For the second question, define
$$r_1=\sqrt n,\qquad r_{t+1}=\sqrt{n+r_t},$$
and
$$s_1=\sqrt m,\qquad s_{t+1}=\sqrt{m+s_t}.$$
Then
$$A_k=\sqrt{m+r_{k-1}}, \qquad B_k=\sqrt{n+s_{k-1}}.$$
Let
$$d_t=s_t-r_t.$$
We shall prove that
$$d_t<m-n$$
for every positive integer $t$.
For $t=1$,
$$d_1=\sqrt m-\sqrt n.$$
Since
$$m-n=(\sqrt m-\sqrt n)(\sqrt m+\sqrt n)$$
and $\sqrt m+\sqrt n>1$, we obtain
$$d_1<m-n.$$
Assume now that
$$d_t<m-n.$$
Then
$$\begin{aligned} d_{t+1} &=\sqrt{m+s_t}-\sqrt{n+r_t}\ &=\frac{(m+s_t)-(n+r_t)} {\sqrt{m+s_t}+\sqrt{n+r_t}}\ &=\frac{(m-n)+d_t} {\sqrt{m+s_t}+\sqrt{n+r_t}}. \end{aligned}$$
By the inductive hypothesis,
$$(m-n)+d_t<2(m-n).$$
Also,
$$m\ge2,\qquad n\ge1,$$
because $m>n$ and both are natural numbers. Hence
$$\sqrt{m+s_t}>1, \qquad \sqrt{n+r_t}>1,$$
so
$$\sqrt{m+s_t}+\sqrt{n+r_t}>2.$$
Therefore
$$d_{t+1} < \frac{2(m-n)}{2} = m-n.$$
The induction is complete, and thus
$$d_t<m-n$$
for all $t$.
Now
$$\begin{aligned} A_k^2-B_k^2 &=(m+r_{k-1})-(n+s_{k-1})\ &=(m-n)-d_{k-1}. \end{aligned}$$
Since $d_{k-1}<m-n$,
$$A_k^2-B_k^2>0.$$
Both numbers are positive, so
$$A_k>B_k.$$
Thus in part 2 the first number is also greater.
Hence the answers are
$$\boxed{\text{In both (1) and (2), the first number is greater.}}$$
Verification of Key Steps
The first delicate point is the estimate $d_1<m-n$. Writing
$$m-n=(\sqrt m-\sqrt n)(\sqrt m+\sqrt n),$$
we see that the factor $\sqrt m+\sqrt n$ exceeds $1$. Dividing by this factor gives
$$\sqrt m-\sqrt n<m-n.$$
If one merely used $\sqrt m>\sqrt n$, the required quantitative bound would not follow.
The second delicate point is the induction step for $d_t$. The identity
$$\sqrt{m+s_t}-\sqrt{n+r_t} = \frac{(m-n)+d_t} {\sqrt{m+s_t}+\sqrt{n+r_t}}$$
must be obtained by rationalization. Replacing the denominator by a weaker bound such as $>1$ would yield only
$$d_{t+1}<(m-n)+d_t,$$
which is insufficient. The proof requires the stronger estimate that the denominator is greater than $2$.
The third delicate point is the final comparison. From $s_{k-1}>r_{k-1}$ one cannot compare $A_k$ and $B_k$ directly. The relevant quantity is
$$A_k^2-B_k^2=(m-n)-d_{k-1},$$
and the whole proof of the lemma is designed precisely to show that this expression remains positive.
Alternative Approaches
For part 1 one may view $(A,B)$ as a solution of
$$A=\sqrt{m+B},\qquad B=\sqrt{n+A}.$$
Subtracting the equations after squaring gives
$$A^2-B^2=(m-n)-(A-B).$$
Factoring yields
$$(A-B)(A+B+1)=m-n.$$
Since the right-hand side is positive and $A+B+1>0$, one immediately obtains $A>B$.
For part 2 one can define
$$g_t(a)=\underbrace{\sqrt{a+\sqrt{a+\cdots+\sqrt a}}}_{t\ \text{root signs}}$$
and prove inductively that
$$g_t(m)-g_t(n)<m-n.$$
The desired comparison then becomes
$$A_k^2-B_k^2=(m-n)-\bigl(g_{k-1}(m)-g_{k-1}(n)\bigr).$$
This route is essentially equivalent to the proof above, but the notation with the sequences $r_t$ and $s_t$ keeps the induction formula more transparent.