Kvant Math Problem 418

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m34s
Source on kvant.digital

Problem

Prove that for any natural number $n$ the following inequalities hold: $$n{\left(!\sqrt[\scriptstyle n~]{n+1}-1\right)}\le 1+\dfrac12+\dfrac13+\ldots+\dfrac1n\le 1+n{\left(1-\dfrac1{!\sqrt[\scriptstyle n~]n}\right)}.$$

Exploration

For small values of $n$,

$$n=1:\qquad 1(\sqrt[1]{2}-1)=1,\qquad H_1=1,\qquad 1+1\left(1-\frac1{\sqrt[1]{1}}\right)=1.$$

For $n=2$,

$$2(\sqrt3-1)\approx1.464,\qquad H_2=\frac32,\qquad 1+2\left(1-\frac1{\sqrt2}\right)\approx1.586.$$

The inequalities hold.

The expressions involving $n$th roots suggest taking logarithms. If

$$a=\sqrt[n]{n+1},$$

then

$$n(a-1)\le H_n \iff a\le 1+\frac{H_n}{n}.$$

Since

$$a^n=n+1,$$

it would suffice to prove

$$\left(1+\frac{H_n}{n}\right)^n\ge n+1.$$

The harmonic sum naturally appears in the product

$$\prod_{k=1}^n\left(1+\frac1k\right)=n+1.$$

Comparing each factor $1+\frac1k$ with the common quantity $1+\frac{H_n}{n}$ suggests the arithmetic mean-geometric mean inequality.

For the upper bound, rewriting gives

$$H_n-1\le n\left(1-\frac1{\sqrt[n]{n}}\right).$$

Equivalently,

$$\frac{n+1-H_n}{n}\ge \frac1{\sqrt[n]{n}}.$$

The quantity $n+1-H_n$ equals

$$\sum_{k=1}^n\left(1-\frac1k\right) =\sum_{k=1}^n\frac{k-1}{k}.$$

Again AM-GM is suggested. The product of the numbers $\frac{k-1}{k}$ for $k\ge2$ is

$$\frac12\cdot\frac23\cdots\frac{n-1}{n}=\frac1n,$$

which matches the appearance of $\sqrt[n]{n}$.

The delicate point is the second inequality, because one must apply AM-GM to $n$ numbers, one of which is $0$, and verify that the resulting geometric mean is indeed $n^{-1/n}$.

Problem Understanding

We must prove that for every natural number $n$, the harmonic sum

$$H_n=1+\frac12+\frac13+\cdots+\frac1n$$

lies between two quantities expressed through $n$th roots:

$$n\bigl(\sqrt[n]{n+1}-1\bigr) \le H_n \le 1+n\left(1-\frac1{\sqrt[n]{n}}\right).$$

This is a Type B problem. The statement is already given and must be proved.

The core difficulty is to connect the harmonic sum with the products

$$\prod_{k=1}^n\left(1+\frac1k\right)=n+1 \quad\text{and}\quad \prod_{k=1}^n\left(1-\frac1k\right)=0,$$

or more precisely with

$$\prod_{k=2}^n\left(1-\frac1k\right)=\frac1n,$$

and then use the arithmetic mean-geometric mean inequality in a suitable form.

Proof Architecture

Lemma 1. The arithmetic mean-geometric mean inequality applied to the numbers $1+\frac1k$ gives

$$1+\frac{H_n}{n}\ge\sqrt[n]{n+1}.$$

The product of these numbers telescopes to $n+1$.

Lemma 2. The arithmetic mean-geometric mean inequality applied to the numbers $1-\frac1k$ for $k=1,\dots,n$ gives

$$\frac{n-H_n+1}{n}\ge \frac1{\sqrt[n]{n}}.$$

Their arithmetic mean equals $\frac{n-H_n+1}{n}$ and their product is $0\cdot\frac1n=0$, but the first term must be handled carefully by writing the geometric mean from the full collection.

A more convenient version is to apply AM-GM to the numbers

$$0,\frac12,\frac23,\dots,\frac{n-1}{n},$$

whose product is $0$, then separate the zero term and compute the remaining geometric mean.

The hardest part is obtaining the upper bound with the correct constant. The step most likely to fail under scrutiny is the computation of the geometric mean associated with the numbers $\frac{k-1}{k}$.

Solution

Let

$$H_n=1+\frac12+\frac13+\cdots+\frac1n.$$

We first prove the left inequality.

Consider the $n$ positive numbers

$$1+\frac11,\quad 1+\frac12,\quad \dots,\quad 1+\frac1n.$$

Their arithmetic mean is

$$\frac1n\sum_{k=1}^n\left(1+\frac1k\right) = 1+\frac{H_n}{n}.$$

Their product is

$$\prod_{k=1}^n\left(1+\frac1k\right) = \prod_{k=1}^n\frac{k+1}{k} = n+1.$$

By the arithmetic mean-geometric mean inequality,

$$1+\frac{H_n}{n} \ge \sqrt[n]{,n+1,}.$$

Hence

$$H_n \ge n\bigl(\sqrt[n]{n+1}-1\bigr),$$

which is the desired lower bound.

Now we prove the right inequality.

Consider the $n$ numbers

$$0,\ \frac12,\ \frac23,\ \dots,\ \frac{n-1}{n}.$$

Their arithmetic mean equals

$$\frac1n\left( 0+\frac12+\frac23+\cdots+\frac{n-1}{n} \right).$$

Since

$$\frac{k-1}{k}=1-\frac1k,$$

we have

$$\sum_{k=1}^n\frac{k-1}{k} = \sum_{k=1}^n\left(1-\frac1k\right) = n-H_n.$$

Therefore the arithmetic mean is

$$\frac{n-H_n}{n}.$$

Apply AM-GM to the $n-1$ positive numbers

$$\frac12,\frac23,\dots,\frac{n-1}{n}.$$

Their product is

$$\frac12\cdot\frac23\cdots\frac{n-1}{n} = \frac1n.$$

Hence

$$\frac1{n-1} \sum_{k=2}^n\frac{k-1}{k} \ge \left(\frac1n\right)^{1/(n-1)}.$$

Using

$$\sum_{k=2}^n\frac{k-1}{k}=n-H_n,$$

we obtain

$$n-H_n \ge (n-1)n^{-1/(n-1)}.$$

It remains to compare the right-hand side with $n^{1-1/n}-1$.

Set

$$t=n^{1/n}\ge1.$$

Then

$$(n-1)n^{-1/(n-1)} = (n-1)t^{-,n/(n-1)}.$$

We claim that

$$(n-1)n^{-1/(n-1)} \ge n^{1-1/n}-1 = \frac{n}{t}-1.$$

Multiplying by the positive quantity $t^{,n/(n-1)}$ gives the equivalent inequality

$$n-1 \ge \left(\frac{n}{t}-1\right)t^{,n/(n-1)}.$$

Since $t^n=n$,

$$\left(\frac{n}{t}-1\right)t^{,n/(n-1)} = t^{,n/(n-1)-1}(t^n-t) = t^{1/(n-1)}(n-t).$$

Thus it suffices to prove

$$n-1\ge t^{1/(n-1)}(n-t).$$

Because $t\ge1$ and $t^{1/(n-1)}\le t$, the right-hand side does not exceed

$$t(n-t).$$

Therefore it is enough to show

$$n-1\ge t(n-t).$$

The latter is equivalent to

$$t^2-nt+n-1\ge0,$$

and

$$t^2-nt+n-1=(t-1)(t-(n-1)).$$

Since $t=n^{1/n}$ satisfies

$$1\le t\le2\le n-1 \qquad (n\ge3),$$

the product is nonnegative. For $n=1$ and $n=2$, the required inequality is checked directly.

Consequently,

$$n-H_n\ge n^{1-1/n}-1.$$

Rearranging,

$$H_n \le n+1-n^{1-1/n} = 1+n\left(1-\frac1{\sqrt[n]{n}}\right).$$

This is the desired upper bound.

The two inequalities are proved.

This completes the proof.

∎

Verification of Key Steps

For the lower bound, the crucial computation is

$$\prod_{k=1}^n\left(1+\frac1k\right) = \frac21\cdot\frac32\cdots\frac{n+1}{n} = n+1.$$

Every intermediate factor cancels. AM-GM then yields

$$1+\frac{H_n}{n}\ge (n+1)^{1/n},$$

which is exactly equivalent to the required inequality.

For the upper bound, the important identity is

$$\prod_{k=2}^n\frac{k-1}{k} = \frac12\cdot\frac23\cdots\frac{n-1}{n} = \frac1n.$$

A careless computation may produce $\frac1{n-1}$ instead of $\frac1n$; the telescoping leaves only the numerator $1$ and denominator $n$.

Another delicate point is the comparison

$$(n-1)n^{-1/(n-1)} \ge n^{1-1/n}-1.$$

After introducing $t=n^{1/n}$, the difference reduces to

$$(t-1)(t-(n-1)).$$

Since $1\le t\le n-1$ for $n\ge3$, this quantity is nonnegative. Missing the factorization obscures the sign completely.

Alternative Approaches

A shorter route uses the concavity of the logarithm. From

$$\log(1+x)\le x$$

for $x>-1$,

$$\log(n+1) = \sum_{k=1}^n\log!\left(1+\frac1k\right) \le H_n.$$

Combining this with

$$e^x\ge1+x$$

gives

$$n+1=e^{\log(n+1)} \le e^{H_n} \le \left(1+\frac{H_n}{n}\right)^n,$$

which yields the lower bound.

For the upper bound one may similarly use

$$-\log(1-x)\ge x \qquad (0<x<1)$$

on the numbers $x=\frac1k$, $k\ge2$, obtaining

$$H_n-1 \le -\log!\left(\frac1n\right) = \log n.$$

Since

$$\log n\le n\left(1-\frac1{\sqrt[n]{n}}\right),$$

the desired estimate follows. The AM-GM approach is preferable because both bounds arise from the same idea and the telescoping products $n+1$ and $1/n$ appear naturally.