Show that the sequence $a_n\leq a_{2n}+a_{2n+1}$ diverges

Question

We are given a sequence $(a_n)$ such that $0\lt a_n\leq a_{2n}+a_{2n+1}$ for all natural numbers $n$. Show that $\sum_{n=1}^\infty a_n$ diverges.

---

I attempted the question as follows. Consider, say, $$\begin{align} S_7 &= a_1+(a_2+a_3)+(a_4+a_5)+(a_6+a_7)\\ &\geq a_1+a_1+(a_2+a_3)\\ &\geq a_1+a_1+a_1 \end{align}$$

But I have no idea how to generalise this to show that the sequence diverges.

Answer 1

What you found can indeed be generalized. Here is a hint:

Take any natural number $n$.

Then $\displaystyle \sum_{k=1}^{2^{n+1}-1} a_k = a_1 + \sum_{k=1}^{2^n-1} ( a_{2k}+a_{2k+1} ) \ge a_1 + \sum_{k=1}^{2^n-1} a_k$.

Thus $\displaystyle \sum_{k=1}^{2^n-1} a_k - \sum_{k=1}^{2^0-1} a_k \ge n·a_1$, by induction.