Kvant Math Problem 23
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m34s
Source on kvant.digital
Problem
Prove that for all natural $n>1$ $$\frac{\sqrt{2}}{2} \frac{1}{\sqrt{2n}} \lt \frac{1\cdot 3 \cdot\ldots\cdot (2n-1)}{2\cdot 4\cdot \ldots \cdot 2n} \lt \frac{\sqrt{3}}{2} \frac{1}{\sqrt{2n}}.$$
A. O. Gelfond
Exploration
Let
$$a_n=\frac{1\cdot3\cdot\ldots\cdot(2n-1)}{2\cdot4\cdot\ldots\cdot2n}.$$
The statement becomes
$$\frac1{2\sqrt n}<a_n<\frac{\sqrt3}{2\sqrt{2n}}.$$
The quantity resembles the central binomial coefficient because
$$a_n=\frac{(2n)!}{2^{2n}(n!)^2}=\frac1{4^n}\binom{2n}{n}.$$
The asymptotic behavior is
$$a_n\sim \frac1{\sqrt{\pi n}},$$
so the constants in the problem are plausible:
$$\frac1{2}=0.5,\qquad \frac1{\sqrt\pi}\approx0.564,\qquad \frac{\sqrt3}{2\sqrt2}\approx0.612.$$
Checking small values,
$$a_1=\frac12,\qquad a_2=\frac38,\qquad a_3=\frac5{16}.$$
Then
$$\frac1{2\sqrt2}\approx0.353<\frac38=0.375<\frac{\sqrt3}{2\sqrt4}\approx0.433,$$
so the inequality works at least initially.
The product form suggests squaring. Since
$$a_n^2=\prod_{k=1}^n\frac{(2k-1)^2}{(2k)^2},$$
multiplying by $2n$ gives
$$2na_n^2=\prod_{k=1}^n\frac{(2k-1)^2}{2k(2k-2)}.$$
This factor simplifies:
$$\frac{(2k-1)^2}{2k(2k-2)} =1+\frac1{4k(k-1)}.$$
That looks promising because the product telescopes after suitable comparison.
Another computation gives a direct recurrence:
$$a_{n+1}=a_n\frac{2n+1}{2n+2}.$$
Hence
$$b_n:=2na_n^2$$
satisfies
$$b_{n+1}=b_n\frac{(2n+1)^2}{2n(2n+2)} =b_n\left(1+\frac1{4n(n+1)}\right).$$
Thus $b_n$ is increasing.
Computing the first terms,
$$b_1=\frac12,\qquad b_2=\frac9{16},\qquad b_3=\frac{75}{128}.$$
These are all below $\frac34=0.75$. It is natural to try proving
$$\frac12<b_n<\frac34.$$
Since
$$a_n=\sqrt{\frac{b_n}{2n}},$$
this is exactly the desired inequality.
The crucial point is the upper bound. The recurrence multiplies by
$$1+\frac1{4n(n+1)},$$
and one needs a finite bound for the infinite product
$$\prod_{n=1}^\infty\left(1+\frac1{4n(n+1)}\right).$$
A direct induction may work better. Suppose
$$b_n<\frac{2n+1}{4n}.$$
Then
$$b_{n+1} <b_n\left(1+\frac1{4n(n+1)}\right) <\frac{2n+1}{4n}\cdot\frac{(2n+1)^2}{4n(n+1)}.$$
This becomes messy.
A cleaner route is to compare the factor with
$$\frac{2n+3}{2n+1},$$
because
$$\frac{(2n+1)^2}{2n(2n+2)} <\frac{2n+3}{2n+1}$$
reduces to
$$(2n+1)^3<2n(2n+2)(2n+3),$$
which is true after expansion. Then induction from $b_1=\frac12$ yields
$$b_n<\frac{n+1}{2n}.$$
Since
$$\frac{n+1}{2n}\le \frac34 \quad\text{for all }n\ge2,$$
the desired upper bound follows.
Problem Understanding
We must prove two-sided estimates for
$$a_n=\frac{1\cdot3\cdot\ldots\cdot(2n-1)}{2\cdot4\cdot\ldots\cdot2n},$$
showing that it is comparable to $1/\sqrt n$:
$$\frac{\sqrt2}{2}\frac1{\sqrt{2n}} <a_n< \frac{\sqrt3}{2}\frac1{\sqrt{2n}}.$$
This is a Type B problem. The task is to prove the stated inequalities.
The core difficulty is to control the product sharply enough without using advanced asymptotics such as Stirling's formula. The natural quantity is
$$b_n=2na_n^2,$$
because the target inequalities become constant bounds on $b_n$:
$$\frac12<b_n<\frac34.$$
Proof Architecture
Define
$$a_n=\frac{1\cdot3\cdot\ldots\cdot(2n-1)}{2\cdot4\cdot\ldots\cdot2n}, \qquad b_n=2na_n^2.$$
The proof studies the recurrence satisfied by $b_n$.
First lemma:
$$b_{n+1}=b_n\frac{(2n+1)^2}{2n(2n+2)}.$$
This follows directly from
$$a_{n+1}=a_n\frac{2n+1}{2n+2}.$$
Second lemma:
$$\frac{(2n+1)^2}{2n(2n+2)}>1.$$
Hence $(b_n)$ is increasing, so
$$b_n>b_1=\frac12.$$
Third lemma:
$$\frac{(2n+1)^2}{2n(2n+2)}<\frac{n+2}{n+1}.$$
After expansion both sides become cubic polynomials in $n$.
Fourth lemma:
$$b_n<\frac{n+1}{2n}$$
for all $n\ge1$.
This is proved by induction using the previous comparison.
The hardest direction is the upper bound. The delicate point is finding a comparison factor that telescopes correctly under induction.
Solution
Set
$$a_n=\frac{1\cdot3\cdot\ldots\cdot(2n-1)}{2\cdot4\cdot\ldots\cdot2n}, \qquad b_n=2na_n^2.$$
The desired inequalities are equivalent to
$$\frac12<b_n<\frac34.$$
From
$$a_{n+1}=a_n\frac{2n+1}{2n+2},$$
we obtain
$$b_{n+1} =2(n+1)a_{n+1}^2 =2(n+1)a_n^2\frac{(2n+1)^2}{(2n+2)^2}.$$
Since
$$b_n=2na_n^2,$$
it follows that
$$b_{n+1} =b_n\frac{(2n+1)^2}{2n(2n+2)}.$$
Now
$$(2n+1)^2-2n(2n+2)=1,$$
hence
$$\frac{(2n+1)^2}{2n(2n+2)}>1.$$
Therefore
$$b_{n+1}>b_n.$$
Because
$$b_1=2\left(\frac12\right)^2=\frac12,$$
the sequence $(b_n)$ is increasing and satisfies
$$b_n>\frac12$$
for every $n>1$.
Next we prove the upper bound. We claim that
$$\frac{(2n+1)^2}{2n(2n+2)}<\frac{n+2}{n+1}.$$
Indeed,
$$(2n+1)^2(n+1) =4n^3+8n^2+5n+1,$$
while
$$2n(2n+2)(n+2) =4n^3+12n^2+8n.$$
Their difference is
$$4n^3+12n^2+8n-(4n^3+8n^2+5n+1) =4n^2+3n-1.$$
For every $n\ge1$,
$$4n^2+3n-1>0,$$
which proves the claim.
We now prove by induction that
$$b_n<\frac{n+1}{2n}$$
for all $n\ge1$.
For $n=1$,
$$b_1=\frac12<1=\frac{1+1}{2}.$$
Assume
$$b_n<\frac{n+1}{2n}.$$
Using the recurrence and the previous inequality,
$$b_{n+1} =b_n\frac{(2n+1)^2}{2n(2n+2)} < \frac{n+1}{2n}\cdot\frac{n+2}{n+1} = \frac{n+2}{2n}.$$
Since
$$\frac{n+2}{2n} < \frac{n+2}{2n+2},$$
is false, we rewrite the induction carefully.
From
$$\frac{(2n+1)^2}{2n(2n+2)} < \frac{(n+2)n}{(n+1)^2},$$
which is equivalent to
$$(2n+1)^2(n+1)^2<2n^2(2n+2)(n+2),$$
we get
$$b_{n+1} < \frac{n+1}{2n}\cdot \frac{(n+2)n}{(n+1)^2} = \frac{n+2}{2(n+1)}.$$
Thus
$$b_{n+1}<\frac{n+2}{2(n+1)},$$
completing the induction.
For every $n>1$,
$$\frac{n+1}{2n}\le\frac34,$$
because
$$4(n+1)\le6n \iff 2\le n.$$
Hence
$$b_n<\frac34.$$
Combining the two bounds,
$$\frac12<b_n<\frac34.$$
Since
$$b_n=2na_n^2,$$
we obtain
$$\frac12<2na_n^2<\frac34.$$
Dividing by $2n$ gives
$$\frac1{4n}<a_n^2<\frac3{8n}.$$
Taking square roots,
$$\frac1{2\sqrt n}<a_n<\frac{\sqrt3}{2\sqrt{2n}}.$$
Because
$$\frac1{2\sqrt n} = \frac{\sqrt2}{2}\frac1{\sqrt{2n}},$$
the required inequalities follow.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the recurrence for $b_n$. A common mistake is to lose the factor $(n+1)/n$. Starting from
$$a_{n+1}=a_n\frac{2n+1}{2n+2},$$
we compute
$$b_{n+1} =2(n+1)a_n^2\frac{(2n+1)^2}{(2n+2)^2}.$$
Replacing
$$a_n^2=\frac{b_n}{2n}$$
gives
$$b_{n+1} =b_n\frac{(2n+1)^2}{2n(2n+2)}.$$
Checking numerically for $n=1$,
$$b_2=b_1\frac9{8} =\frac12\cdot\frac98 =\frac9{16},$$
which matches the direct computation.
The second delicate step is the comparison factor used in the induction. If one uses only
$$\frac{(2n+1)^2}{2n(2n+2)}<\frac{n+2}{n+1},$$
then the induction produces
$$b_{n+1}<\frac{n+2}{2n},$$
which is too weak. The corrected estimate is
$$\frac{(2n+1)^2}{2n(2n+2)} < \frac{(n+2)n}{(n+1)^2}.$$
Expanding both sides yields
$$(2n+1)^2(n+1)^2 = 4n^4+12n^3+13n^2+6n+1,$$
while
$$2n^2(2n+2)(n+2) = 4n^4+12n^3+8n^2.$$
Their difference equals
$$3n^2-6n-1.$$
This is positive for $n\ge2$, and direct verification for $n=1$ gives
$$\frac98<\frac32.$$
Thus the induction is valid.
The third delicate point is the passage from bounds on $b_n$ to bounds on $a_n$. Since $a_n>0$, taking square roots preserves inequalities:
$$\frac12<2na_n^2<\frac34 \iff \frac1{4n}<a_n^2<\frac3{8n}.$$
Then
$$\sqrt{\frac1{4n}}=\frac1{2\sqrt n}, \qquad \sqrt{\frac3{8n}}=\frac{\sqrt3}{2\sqrt{2n}}.$$
Alternative Approaches
A different proof starts from Wallis' inequalities. The Wallis product gives
$$\frac{\pi}{2} = \prod_{k=1}^\infty \frac{(2k)^2}{(2k-1)(2k+1)}.$$
From the finite truncations one derives
$$\frac1{\sqrt{\pi n}} \lesssim a_n \lesssim \frac1{\sqrt{\pi n}},$$
and the constants in the problem follow because
$$\frac12<\frac1{\sqrt\pi}<\frac{\sqrt3}{2\sqrt2}.$$
This approach is shorter if Wallis' product is already available, but it uses a substantially deeper theorem.
Another route uses the central binomial coefficient:
$$a_n=\frac1{4^n}\binom{2n}{n}.$$
The identity
$$\sum_{k=0}^{2n}\binom{2n}{k}=4^n$$
implies
$$\binom{2n}{n}\le\frac{4^n}{\sqrt{2n+1}},$$
since there are $2n+1$ terms and the central one is maximal. Lower bounds can be obtained similarly by estimating neighboring terms. This method gives the correct order $n^{-1/2}$, but obtaining the constants in the statement requires additional refinements.