Maths Olympiad Prep

Library / /13 of 32

Algebra Difficulty 5.6 AIME, harder Prove it Estonia

A positive integer nn is written on the board once, then n1n-1 is written on the board twice, etc.; on every step the number smaller by 11 from the previous number is written twice as many times as the previous number. When reaching zeros this process stops. Prove that in the end the sum of the numbers on the board is less than 2n+12^{n+1}.

Solution

The sum of the numbers on the board is
sn=1n+2(n1)+4(n2)++2n11. s_n = 1 \cdot n + 2 \cdot (n-1) + 4 \cdot (n-2) + \dots + 2^{n-1} \cdot 1.
Let us also define
rn=sn2n=121+142+183++12nn. r_n = \frac{s_n}{2^n} = \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 + \frac{1}{8} \cdot 3 + \dots + \frac{1}{2^n} \cdot n.

12+14++12n+1<12+14+=1\frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^{n+1}} < \frac{1}{2} + \frac{1}{4} + \dots = 1. Thus rn<2r_n < 2 always implies rn+1<rn2+1<1+1=2r_{n+1} < \frac{r_n}{2} + 1 < 1 + 1 = 2. As r1=12<2r_1 = \frac{1}{2} < 2, we have rn<2r_n < 2 for every n1n \ge 1. From there we get that sn=2nrn<2n+1s_n = 2^n \cdot r_n < 2^{n+1} for every n1n \ge 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.