Putnam 1994, Question 1

by ayushkhaitan3437

Just want to record a solution to a relatively simple Putnam problem here. The problem is the following:

Show that a sequence a_1,a_2,a_2,\dots satisfies the condition 0<a_n\leq a_{2n}+a_{2n+1}. Prove that \sum a_i diverges.

I tried attacking it with the usual methods of showing that a sequence diverges, but nothing seemed to work. However, every good Olympiad worth its salt asks for some experimentation, which will then yield important observations/patterns. I did the same here.

Without loss of generality, let a_1=1. Then a_2+a_3\geq a_1=1. Hence, a_2+a_3\geq 1. Similary, a_4+a_5\geq a_2 and a_6+a_7\geq a_3. Therefore, a_4+a_5+a_6+a_7\geq a_2+a_3\geq 1. Continuing this pattern, we observe that for all n\in\Bbb{N}, a_{2^n}+\dots+a_{2^{n+1}-1}\geq 1. Hence \sum a_i, which can be thought of as \sum\limits_{n=1}^{\infty}(a_{2^n}+\dots+a_{2^{n+1}-1}), diverges.