Maths Olympiad Prep

Library / /106 of 158

Algebra Difficulty 6.3 National Olympiad Prove it Estonia

Prove that for any positive integer nn, 2343nn1>n2 \cdot \sqrt{3} \cdot \sqrt[3]{4} \cdot \dots \cdot \sqrt[n-1]{n} > n.

Solution

For 2kn2 \le k \le n, the GM-HM inequality for the numbers k,,k,1k, \dots, k, 1, with kk repeated k2k-2 times, gives
k1=(k1)2k1=k(k2)+1k1kk2k1=kk1kk1=kkk1 k - 1 = \frac{(k - 1)^2}{k - 1} = \frac{k(k - 2) + 1}{k - 1} \ge \sqrt[k-1]{k^{k-2}} = \sqrt[k-1]{\frac{k^{k-1}}{k}} = \frac{k}{\sqrt[k-1]{k}}
Hence kk1kk1\sqrt[k-1]{k} \ge \frac{k}{k-1} for every k=2,3,,nk = 2, 3, \dots, n, with equality only for k=2k = 2. Therefore
2343nn1>213243nn1=n. 2 \cdot \sqrt{3} \cdot \sqrt[3]{4} \cdot \dots \cdot \sqrt[n-1]{n} > \frac{2}{1} \cdot \frac{3}{2} \cdot \frac{4}{3} \cdot \dots \cdot \frac{n}{n-1} = n.

Solution 2:
For 2kn2 \le k \le n, the HM-GM inequality for the numbers 1,,1,k1, \dots, 1, k (with 11 repeated k2k-2 times) gives
kk1k1k2+1k=(k1)k(k2)k+1=(k1)k(k1)2=kk1, \sqrt[k-1]{k} \ge \frac{k-1}{k-2 + \frac{1}{k}} = \frac{(k-1)k}{(k-2)k+1} = \frac{(k-1)k}{(k-1)^2} = \frac{k}{k-1},
with equality only for k=2k=2. We continue as in solution 1.

Solution 3:
From the binomial theorem,
(kk1)k1=(1+1k1)k1=(k10)(k1)0+(k11)(k1)1++(k1k1)(k1)k1. \left(\frac{k}{k-1}\right)^{k-1} = \left(1 + \frac{1}{k-1}\right)^{k-1} = \frac{\binom{k-1}{0}}{(k-1)^0} + \frac{\binom{k-1}{1}}{(k-1)^1} + \dots + \frac{\binom{k-1}{k-1}}{(k-1)^{k-1}}.
There are kk summands, of which (k10)(k1)0=(k11)(k1)1=1\frac{\binom{k-1}{0}}{(k-1)^0} = \frac{\binom{k-1}{1}}{(k-1)^1} = 1, and for 1<ik11 < i \le k-1
(k1i)(k1)i=(k1)(ki)i!(k1)i<(k1)(ki)(k1)i<1. \frac{\binom{k-1}{i}}{(k-1)^i} = \frac{(k-1) \cdots (k-i)}{i! (k-1)^i} < \frac{(k-1) \cdots (k-i)}{(k-1)^i} < 1.
Therefore (kk1)k11+1++1k times=k\left(\frac{k}{k-1}\right)^{k-1} \le \underbrace{1 + 1 + \dots + 1}_{k \text{ times}} = k, whence kk1kk1\sqrt[k-1]{k} \ge \frac{k}{k-1}, with equality only for k=2k=2. We continue as in solution 1.

Solution 4:
We show that kk>(k+1)k1k^k > (k+1)^{k-1} for k2k \ge 2. The case k=2k=2 is obvious. Suppose now that kk>(k+1)k1k^k > (k+1)^{k-1} holds for some kk, and let's prove (k+1)k+1>(k+2)k(k+1)^{k+1} > (k+2)^k. Note that (k+1)k+1(k+1)k1=(k+1)2k=(k2+2k+1)k>(k2+2k)k=(k(k+2))k=kk(k+2)k(k+1)^{k+1} \cdot (k+1)^{k-1} = (k+1)^{2k} = (k^2+2k+1)^k > (k^2+2k)^k = (k(k+2))^k = k^k \cdot (k+2)^k, giving (k+1)k+1kk>(k+2)k(k+1)k1\frac{(k+1)^{k+1}}{k^k} > \frac{(k+2)^k}{(k+1)^{k-1}}. This combined with the induction assumption gives
(k+1)k+1=(k+1)k+1kkkk>(k+2)k(k+1)k1(k+1)k1=(k+2)k. (k+1)^{k+1} = \frac{(k+1)^{k+1}}{k^k} \cdot k^k > \frac{(k+2)^k}{(k+1)^{k-1}} \cdot (k+1)^{k-1} = (k+2)^k.
We have proven kk>(k+1)k1k^k > (k+1)^{k-1}, which is equivalent to kk1>k+1k\sqrt[k-1]{k} > \sqrt[k]{k+1}. Therefore kk1>nk\sqrt[k-1]{k} > \sqrt[k]{n} for k=2,3,,n1k=2, 3, \dots, n-1, and
2343nn1>(nn1)n1=n. 2 \cdot \sqrt{3} \cdot \sqrt[3]{4} \cdots \sqrt[n-1]{n} > (\sqrt[n-1]{n})^{n-1} = n.

Solution 5:
We give another proof for the inequality kk>(k+1)k1k^k > (k+1)^{k-1}. It is equivalent to k(kk+1)k1>1k \cdot \left(\frac{k}{k+1}\right)^{k-1} > 1, or kkk+1kk+1k1 times>1k \cdot \underbrace{\frac{k}{k+1} \cdots \frac{k}{k+1}}_{k-1 \text{ times}} > 1. Note that for x<k+1x < k+1, xxkk+1=x(1kk+1)=x1k+1<1x-x \cdot \frac{k}{k+1} = x \cdot (1-\frac{k}{k+1}) = x \cdot \frac{1}{k+1} < 1. Therefore, multiplication with each factor kk+1\frac{k}{k+1} decreases the product by less than 1; cumulatively the product becomes smaller by less than k1k-1. Therefore k(kk+1)k1>k(k1)=1k \cdot \left(\frac{k}{k+1}\right)^{k-1} > k-(k-1)=1.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.