A positive integer n is written on the board once, then n−1 is written on the board twice, etc.; on every step the number smaller by 1 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+1.
Solution
The sum of the numbers on the board is sn=1⋅n+2⋅(n−1)+4⋅(n−2)+⋯+2n−1⋅1. Let us also define rn=2nsn=21⋅1+41⋅2+81⋅3+⋯+2n1⋅n.
21+41+⋯+2n+11<21+41+⋯=1. Thus rn<2 always implies rn+1<2rn+1<1+1=2. As r1=21<2, we have rn<2 for every n≥1. From there we get that sn=2n⋅rn<2n+1 for every n≥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.