Maths Olympiad Prep

Library / /12 of 61

Algebra Difficulty 5.6 AIME, harder Prove it Belarus

For every integer n2n \ge 2 prove the inequality
12!+23!++2n2n!32, \frac{1}{2!} + \frac{2}{3!} + \dots + \frac{2^{n-2}}{n!} \le \frac{3}{2},
where k!=12kk! = 1 \cdot 2 \cdot \dots \cdot k.

Solution

Transform the expression on the left side
12!+23!++2n2n!=12!(1+23+2234++2n234n)12(1+23+2232++2n23n2)=12(1+23+(23)2++(23)n2)12(1+23+(23)2++(23)n2+)=121123=32. \begin{aligned} \frac{1}{2!} + \frac{2}{3!} + \dots + \frac{2^{n-2}}{n!} &= \frac{1}{2!} \left( 1 + \frac{2}{3} + \frac{2^2}{3 \cdot 4} + \dots + \frac{2^{n-2}}{3 \cdot 4 \dots n} \right) \\ &\le \frac{1}{2} \left( 1 + \frac{2}{3} + \frac{2^2}{3^2} + \dots + \frac{2^{n-2}}{3^{n-2}} \right) \\ &= \frac{1}{2} \left( 1 + \frac{2}{3} + \left( \frac{2}{3} \right)^2 + \dots + \left( \frac{2}{3} \right)^{n-2} \right) \\ &\le \frac{1}{2} \left( 1 + \frac{2}{3} + \left( \frac{2}{3} \right)^2 + \dots + \left( \frac{2}{3} \right)^{n-2} + \dots \right) \\ &= \frac{1}{2} \cdot \frac{1}{1 - \frac{2}{3}} = \frac{3}{2}. \end{aligned}

Second solution:

We will prove by induction a stronger inequality
12!+23!++2n2n!321n,() \frac{1}{2!} + \frac{2}{3!} + \dots + \frac{2^{n-2}}{n!} \le \frac{3}{2} - \frac{1}{n}, \quad (*)
from which, obviously, follows the required. It is easy to check that at n=2,3,4,5n = 2, 3, 4, 5 the inequality ()(*) holds — it is the base of induction.

Induction step: assume that the inequality ()(*) is true for some n=kn = k. To prove ()(*) for n=k+1n = k+1 it is enough to show that the right side of this inequality increases faster than the left side, i.e. it is enough to prove the inequality
2k1(k+1)!1k1k+1=1k(k+1). \frac{2^{k-1}}{(k+1)!} \le \frac{1}{k} - \frac{1}{k+1} = \frac{1}{k(k+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 and solution reproduced as published; topic and difficulty added by this site.