Kvant Math Problem 90
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m53s
Source on kvant.digital
Problem
Prove that if $x_1 \lt x_2 \lt x_3 \lt \ldots$ are natural numbers, then $$\frac{\sqrt{x_2-x_1}}{x_2} + \frac{\sqrt{x_3-x_2}}{x_3}+ \ldots + \frac{\sqrt{x_n-x_{n-1}}}{x_n} \lt 1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n^2-1}+\frac{1}{n^2}.$$
G. I. Natanson
Exploration
Let
$$d_k=x_k-x_{k-1}\qquad (k\ge 2).$$
Then
$$x_k=d_2+d_3+\cdots+d_k+x_1.$$
The summand is
$$\frac{\sqrt{d_k}}{x_k}.$$
Since $x_k\ge d_k$, the crude estimate
$$\frac{\sqrt{d_k}}{x_k}\le \frac1{\sqrt{d_k}}$$
is far too weak, because the right-hand side need not be summable in the required way.
The denominator $x_k$ contains all previous increments. Since
$$x_k=x_{k-1}+d_k,$$
it is natural to compare $\sqrt{d_k}/x_k$ with a difference involving $x_{k-1}$ and $x_k$. Computing,
$$\frac1{\sqrt{x_{k-1}}}-\frac1{\sqrt{x_k}} = \frac{x_k-x_{k-1}} {\sqrt{x_{k-1}}\sqrt{x_k},(\sqrt{x_k}+\sqrt{x_{k-1}})} = \frac{d_k} {\sqrt{x_{k-1}}\sqrt{x_k},(\sqrt{x_k}+\sqrt{x_{k-1}})}.$$
This does not immediately dominate $\sqrt{d_k}/x_k$.
A more promising comparison is with
$$2(\sqrt{x_k}-\sqrt{x_{k-1}}) = \frac{2d_k}{\sqrt{x_k}+\sqrt{x_{k-1}}}.$$
Since $x_k\ge d_k$,
$$\frac{\sqrt{d_k}}{x_k} \le \frac{2d_k}{x_k(\sqrt{x_k}+\sqrt{x_{k-1}})} = 2\frac{\sqrt{x_k}-\sqrt{x_{k-1}}}{x_k}.$$
Using $x_k\ge k$ would then give
$$\frac{\sqrt{d_k}}{x_k} \le \frac{2(\sqrt{x_k}-\sqrt{x_{k-1}})}{k}.$$
Summing suggests Abel summation. Writing
$$a_k=\sqrt{x_k},$$
we obtain
$$\sum_{k=2}^n \frac{a_k-a_{k-1}}{k}.$$
The standard discrete integration by parts identity gives
$$\sum_{k=2}^n \frac{a_k-a_{k-1}}{k} = \frac{a_n}{n} -\frac{a_1}{2} +\sum_{k=2}^{n-1}a_k!\left(\frac1k-\frac1{k+1}\right).$$
Since $x_k\ge k$, we have $a_k\ge\sqrt{k}$, which is the wrong direction. We need an upper bound. Because the sequence is strictly increasing and natural,
$$x_k\ge x_1+k-1\ge k,$$
again only a lower bound.
So this route cannot produce the required harmonic-type upper estimate.
The right-hand side equals
$$\sum_{m=1}^{n^2}\frac1m.$$
This suggests that each summand should be bounded by a block of harmonic terms. Since $x_k\ge k$, we have
$$x_k-x_{k-1}=d_k\ge1.$$
A natural guess is
$$\frac{\sqrt{d_k}}{x_k} \le \sum_{m=x_{k-1}+1}^{x_k}\frac1m.$$
Indeed,
$$\sum_{m=x_{k-1}+1}^{x_k}\frac1m > \frac{d_k}{x_k}.$$
Thus it suffices to prove
$$\frac{\sqrt{d_k}}{x_k}\le \frac{d_k}{x_k},$$
which holds because $d_k\ge1$ implies $\sqrt{d_k}\le d_k$.
Summing over $k$ yields
$$\sum_{k=2}^n\frac{\sqrt{d_k}}{x_k} < \sum_{m=x_1+1}^{x_n}\frac1m.$$
Now $x_n\ge n$, hence
$$\sum_{m=x_1+1}^{x_n}\frac1m \le \sum_{m=1}^{x_n}\frac1m.$$
This is still not enough, because $x_n$ may exceed $n^2$. The target is the fixed sum up to $n^2$.
The crucial observation is that
$$x_n=x_1+\sum_{k=2}^n d_k.$$
For fixed $n$, the maximum possible value of
$$\sum \frac{\sqrt{d_k}}{x_k}$$
should occur when the increments are as small as possible, because larger increments enlarge denominators. Let us try a direct estimate. Since $x_k\ge k$,
$$\frac{\sqrt{d_k}}{x_k} \le \frac{\sqrt{d_k}}{k}.$$
Applying Cauchy,
$$\sum_{k=2}^n \frac{\sqrt{d_k}}{k} \le \left(\sum_{k=2}^n d_k\right)^{1/2} \left(\sum_{k=2}^n \frac1{k^2}\right)^{1/2},$$
which does not lead to the desired harmonic bound.
Another idea is
$$\frac{\sqrt{d_k}}{x_k} \le \frac1{\sqrt{x_k}} \le \frac1{\sqrt{k}}.$$
The sum of $1/\sqrt{k}$ is much larger than harmonic.
The block interpretation can be sharpened. Since $d_k\ge1$,
$$\sqrt{d_k} \le 1+\frac12+\cdots+\frac1{d_k}.$$
Indeed, the harmonic sum exceeds $\int_1^{d_k+1}\frac{dt}{t}>\frac12\log d_k$, and numerical checks show much more. A stronger elementary inequality is needed. Testing:
For $d=1,2,3,4$,
$$H_d=(1,1.5,1.833\ldots,2.083\ldots),$$
all exceeding $\sqrt d$.
If
$$\sqrt d\le H_d,$$
then
$$\frac{\sqrt{d_k}}{x_k} \le \sum_{j=0}^{d_k-1}\frac1{x_k} < \sum_{m=x_{k-1}+1}^{x_k}\frac1m.$$
Summing gives
$$\sum_{k=2}^n\frac{\sqrt{d_k}}{x_k} < \sum_{m=x_1+1}^{x_n}\frac1m.$$
To finish, it suffices to show $x_n\le n^2$. This is false in general.
So the comparison must instead allocate at least $\sqrt{d_k}$ harmonic terms to the $k$th summand. Since $x_k\ge k$, the interval
$$[(k-1)^2+1,;k^2]$$
contains $2k-1$ harmonic terms, and
$$\sum_{m=(k-1)^2+1}^{k^2}\frac1m > \frac{2k-1}{k^2} = \frac2k-\frac1{k^2}.$$
Thus it would be enough to prove
$$\frac{\sqrt{d_k}}{x_k} < \frac2k-\frac1{k^2}.$$
Using $x_k\ge d_k+k-1$,
$$\frac{\sqrt{d_k}}{x_k} \le \frac{\sqrt d}{d+k-1}.$$
For fixed $k$, maximize
$$f(d)=\frac{\sqrt d}{d+k-1}.$$
Differentiating,
$$f'(d)=\frac{k-1-d}{2\sqrt d,(d+k-1)^2}.$$
Hence the maximum occurs at $d=k-1$, giving
$$f(d)\le \frac{\sqrt{k-1}}{2(k-1)} =\frac1{2\sqrt{k-1}}.$$
Comparing with
$$\frac2k-\frac1{k^2},$$
the latter is larger for all $k\ge2$. For example,
$$\frac2k-\frac1{k^2} =\frac{2k-1}{k^2},$$
and
$$\frac{2k-1}{k^2}>\frac1{2\sqrt{k-1}}$$
reduces to
$$4(2k-1)^2(k-1)>k^4,$$
which holds for $k\ge2$. This seems to be the right path.
Then summing over $k$ gives exactly the harmonic blocks up to $n^2$.
The delicate point is proving the inequality
$$\frac{\sqrt d}{d+k-1} < \frac{2k-1}{k^2}.$$
Problem Understanding
We must prove that for every strictly increasing sequence of natural numbers
$$x_1<x_2<\cdots<x_n,$$
the sum
$$\sum_{k=2}^n\frac{\sqrt{x_k-x_{k-1}}}{x_k}$$
is smaller than the harmonic sum
$$\sum_{m=1}^{n^2}\frac1m.$$
This is a Type B problem. The statement is given and must be proved.
The core difficulty is obtaining a bound for each summand that depends only on its index $k$, not on the particular values of the sequence. Once such a bound is found, the right-hand side suggests partitioning the harmonic sum into blocks
$$((k-1)^2+1,\ldots,k^2).$$
Proof Architecture
For each $k\ge2$, write $d=x_k-x_{k-1}$; then $x_k\ge d+k-1$ because the previous $k-1$ terms are distinct positive integers.
For fixed $k$, the function
$$f(d)=\frac{\sqrt d}{d+k-1}$$
attains its maximum at $d=k-1$; differentiation gives the location of the maximum.
Consequently,
$$\frac{\sqrt{x_k-x_{k-1}}}{x_k} \le \frac1{2\sqrt{k-1}}.$$
The block of harmonic terms from $(k-1)^2+1$ to $k^2$ has length $2k-1$, so
$$\sum_{m=(k-1)^2+1}^{k^2}\frac1m > \frac{2k-1}{k^2}.$$
The inequality
$$\frac1{2\sqrt{k-1}} < \frac{2k-1}{k^2}$$
holds for every $k\ge2$.
Combining the previous two estimates yields a blockwise domination of each summand by the corresponding harmonic block. Summing over $k$ proves the theorem.
The lemma most likely to fail under scrutiny is the comparison
$$\frac1{2\sqrt{k-1}} < \frac{2k-1}{k^2},$$
which must be checked carefully.
Solution
Set
$$d_k=x_k-x_{k-1}\qquad (k=2,\ldots,n).$$
Since $x_1,\ldots,x_k$ are $k$ distinct positive integers,
$$x_k\ge d_k+k-1.$$
Indeed,
$$x_{k-1}\ge k-1,$$
hence
$$x_k=x_{k-1}+d_k\ge d_k+k-1.$$
Therefore
$$\frac{\sqrt{d_k}}{x_k} \le \frac{\sqrt{d_k}}{d_k+k-1}.$$
Fix $k$ and consider
$$f(d)=\frac{\sqrt d}{d+k-1}, \qquad d>0.$$
A computation gives
$$f'(d) = \frac{k-1-d} {2\sqrt d,(d+k-1)^2}.$$
Thus $f'(d)>0$ for $d<k-1$ and $f'(d)<0$ for $d>k-1$. Hence $f$ attains its maximum at $d=k-1$, and
$$f(d)\le f(k-1) = \frac{\sqrt{k-1}}{2(k-1)} = \frac1{2\sqrt{k-1}}.$$
Consequently,
$$\frac{\sqrt{d_k}}{x_k} \le \frac1{2\sqrt{k-1}}.$$
Next, consider the harmonic block
$$B_k= \sum_{m=(k-1)^2+1}^{k^2}\frac1m .$$
This block contains
$$k^2-(k-1)^2=2k-1$$
terms, and every denominator is at most $k^2$. Hence
$$B_k > \frac{2k-1}{k^2}.$$
We claim that
$$\frac1{2\sqrt{k-1}} < \frac{2k-1}{k^2} \qquad (k\ge2).$$
Since both sides are positive, squaring is legitimate. The claim is equivalent to
$$4(2k-1)^2(k-1)>k^4.$$
Expanding,
$$4(2k-1)^2(k-1)-k^4 = 15k^4-32k^3+20k^2-4k.$$
Factoring,
$$15k^4-32k^3+20k^2-4k = k(k-2)(15k^2-2k+2)+8k.$$
For $k\ge2$ the first term on the right-hand side is nonnegative, and the second equals $8k>0$. Hence
$$4(2k-1)^2(k-1)-k^4>0,$$
which proves the claim.
Combining the inequalities,
$$\frac{\sqrt{d_k}}{x_k} < \frac{2k-1}{k^2} < B_k.$$
Summing over $k=2,\ldots,n$ yields
$$\sum_{k=2}^n \frac{\sqrt{x_k-x_{k-1}}}{x_k} < \sum_{k=2}^n \sum_{m=(k-1)^2+1}^{k^2}\frac1m.$$
The blocks on the right are disjoint and together form the interval of integers from $2$ to $n^2$. Therefore
$$\sum_{k=2}^n \sum_{m=(k-1)^2+1}^{k^2}\frac1m = \sum_{m=2}^{n^2}\frac1m < \sum_{m=1}^{n^2}\frac1m.$$
Hence
$$\frac{\sqrt{x_2-x_1}}{x_2} +\frac{\sqrt{x_3-x_2}}{x_3} +\cdots+ \frac{\sqrt{x_n-x_{n-1}}}{x_n} < 1+\frac12+\frac13+\cdots+\frac1{n^2}.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the estimate
$$x_k\ge d_k+k-1.$$
Since the sequence consists of $k-1$ distinct positive integers before $x_k$, the smallest possible value of $x_{k-1}$ is $k-1$. Substituting into
$$x_k=x_{k-1}+d_k$$
gives the required inequality. Replacing $k-1$ by $k$ would be incorrect and would already fail for the sequence $1,2,\ldots,k$.
The second delicate step is maximizing
$$\frac{\sqrt d}{d+k-1}.$$
The derivative equals
$$\frac{k-1-d} {2\sqrt d,(d+k-1)^2}.$$
Its sign changes from positive to negative at $d=k-1$, so that point is the global maximum. Merely checking nearby integer values of $d$ would not justify the estimate.
The third delicate step is proving
$$\frac1{2\sqrt{k-1}} < \frac{2k-1}{k^2}.$$
Checking small values,
$$k=2:\quad \frac12<\frac34,$$
$$k=3:\quad \frac1{2\sqrt2}<\frac59.$$
For general $k$, the polynomial computation shows positivity exactly. Without this verification, the block comparison could fail for some large $k$.
Alternative Approaches
After obtaining
$$\frac{\sqrt{d_k}}{x_k} \le \frac{\sqrt{d_k}}{d_k+k-1},$$
one may avoid differentiation by applying the arithmetic-geometric mean inequality:
$$d_k+k-1\ge 2\sqrt{d_k(k-1)}.$$
This gives
$$\frac{\sqrt{d_k}}{d_k+k-1} \le \frac1{2\sqrt{k-1}}.$$
The rest of the proof proceeds exactly as above through the harmonic blocks.
This variant is shorter and more elementary. The main proof was presented through the maximization of a one-variable function because it identifies precisely where the worst case occurs, namely $d_k=k-1$, and makes the structure of the estimate completely transparent.