Maths Olympiad Prep

Library / Belarusian Mathematical Olympiad /57 of 208

Belarusian Mathematical Olympiad

Algebra Difficulty 5.6 AIME, harder Prove it Belarus

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

Solution

Transform the expression on the left side
12!+23!+⋯+2n−2n!=12!(1+23+223⋅4+⋯+2n−23⋅4…n)≤12(1+23+2232+⋯+2n−23n−2)=12(1+23+(23)2+⋯+(23)n−2)≤12(1+23+(23)2+⋯+(23)n−2+… )=12⋅11−23=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!+⋯+2n−2n!≤32−1n,(∗) \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
2k−1(k+1)!≤1k−1k+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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.