Proof check for Putnam practice problem I realize this is simply an A1 problem, but my proof seems way too simple, so I would like someone to point out whether or not it's correct (and most importantly, fix any flaws in it).
Problem.
Suppose that a sequence $a_1, a_2, a_3, ...$ satisfies $0 < a_n \leq a_{2n} + a_{2n+1}$ for all $n \geq 1$. Prove that the series $\sum _{n = 1} ^\infty a_n$ diverges.
Solution. From the given conditions, $$a_1 \leq a_2 + a_3 \leq a_4 + a_5 + a_6 + a_7 \leq \ . \ . \ 
.$$
Thus, $$a_1 + (a_2 + a_3) + (a_4 + a_5 + a_6 + a_7) + ... \geq a_1 + a_1 + a_1 + ...$$
Which diverges, since $a_1 > 0$.
 A: As I said in a comment above, there is a theorem which says that we can sum by grouping and we
obtain the same sum if the series is convergent. So, this may be added to
your comparison idea to complete the raisonning of the proof as follows.
Assume the series $\sum_{j=1}^{\infty }a_{j},$ converges to some $a,$ then
we have equality of grouping%
$$
\sum_{j=1}^{\infty }a_{j}=\sum_{n=1}^{\infty
}(\sum_{k=2^{n-1}}^{2^{n}-1}a_{k})
$$
but 
$$
(\sum_{k=2^{n-1}}^{2^{n}-1}a_{k})\geq (2^{n}-2^{n-1})a_{1}=2^{n-1}a_{1}
$$
then it must follow that%
$$
\infty >a=\sum_{j=1}^{\infty }a_{j}=\sum_{n=1}^{\infty
}\sum_{k=2^{n-1}}^{2^{n}-1}a_{k}\geq \sum_{n=1}^{\infty
}2^{n-1}a_{1}=a_{1}\sum_{n=1}^{\infty }2^{n-1}=+\infty .
$$
Contradiction.
A: I suppose there is one more thing you could do to be more thorough. They love not giving people points on the Putnam, so it'd be safest to show that the sum diverges by showing that its sequence of partial sums $s_m=\sum _{n=1} ^ma_n$ diverges. So here's what I would do...
Let $m\in\mathbb{N}$. Then $\exists k\in\mathbb{N}$ with $2^k\leq m\leq 2^{k+1}$. [Note that $k$ is the largest natural number less than or equal to $\log_2 m$]
Consider $s_m=\sum _{n=1} ^ma_n=a_1+\cdots+a_m$, the $m^{th}$ partial sum of $\sum _{n=1} ^{\infty}a_n$.
Then $s_m=a_1+\cdots+a_m\geq a_1+\cdots+a_{2^k}$  (since all $a_i>0$).
But, grouping by powers of $2$ (and dropping the final $a_{2^k}$ term) we get: $$s_m\geq a_1+\cdots+a_{2^k}>(a_1)+(a_2+a_3)+(a_4+a_5+a_6+a_7)+\cdots+(a_{2^{k-1}}+\cdots+a_{2^k-1})\geq a_1+a_1+(a_2+a_3)+\cdots+(a_{2^{k-2}}+a_{2^{k-2}+1}+\cdots+a_{2^{k-1}-2}+a_{2^{k-1}-1})\geq a_1+\cdots+a_1=ka_1$$
(There's exactly one $a_1$ per group. Thus there will be  $k\ $ $a_1$'s, since there were k groups [since $2^k-1=2^0+2^1+\cdots+2^{k-1}$])
Since $k$ is the largest natural number less than or equal to $\log_2m$, we know that $k>\log_2m-1$.
Therefore, because $\log_2m\rightarrow \infty$ as $m\rightarrow \infty$, we have that $ka_1\rightarrow \infty$ as $m\rightarrow \infty$.
Hence $s_m$ diverges. Thus $\sum _{n=1} ^{\infty}a_n$ diverges. $\checkmark$
A: I see no flaw in your work, Since $a_{2n}+a_{2n+1}$ will cover all numbers when you sum up the n's from 1 to infinity, you can express this sum as a sum of $a_1$'s which diverges since $a_1>0$, simply showing that since $\sum_{k=1}^{\infty}a_1 \leq \sum_{k=1}^{\infty}a_n$ and $\sum_{k=1}^{\infty} a_1$ diverges, then so must $\sum_{k=1}^{\infty} a_n$
A: In such simple cases, I prefer to resort to proof by induction.  For any positive integer $n$, let $C(n)$ be the claim $$C(n) : S_n = \sum_{k=2^{n-1}}^{2^n-1} a_k \ge a_1.$$  Then the claim $$C(1) : S_1 = a_1 \ge 1 \cdot a_1$$ is trivially true.  Thus there exists at least one positive integer $n$ such that $C(n)$ is true.  Then $$S_{n+1} = \sum_{k=2^n}^{2^{n+1}-1} a_k = \sum_{k=2^{n-1}}^{2^n - 1} a_{2k} + a_{2k+1} \ge \sum_{k=2^{n-1}}^{2^n - 1} a_k = S_n \ge a_1$$ which shows that if $C(n)$ is true, then $C(n+1)$ is also true.  So by the induction hypothesis, $C(n) : S_n \ge a_1$ is true for all positive integers $n$.  It immediately follows that for any positive integer $N$, $$\sum_{k=1}^{2^N-1} a_k = \sum_{n=1}^N S_n \ge N a_1,$$ and since $a_1 > 0$, by the Archimedean property of the reals, for any $M > 0$ there exists a positive integer $N$ for which $N a_1 > M$.
If the infinite sum is convergent, then any sequence of partial sums of its terms without rearrangement must also be bounded; but this contradicts the above conclusion, therefore the sum must diverge.
This proof is rather over-the-top with respect to rigor, but Putnam grading is extremely picky.
