Track / Stage 4 / 202 of 340 #1102 of 2604

Problem 1102

AMC 12 late, AIME early

Algebra Difficulty 4.8 Prove it Berkeley Math Circle Monthly Contest 6 · United States

Let $a_{1}, a_{2}, a_{3}, \ldots$ be an infinite sequence of positive real numbers such that for all $n \geq 1$ ,
$a_{n} \leq a_{2 n}+a_{2 n+1}$
Prove that there exists an $N \geq 1$ such that
$\sum_{n=1}^{N} a_{n}>1$

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:
Let us prove by induction that for any positive integer $k$ , there is an $N$ for which
$\sum_{n=1}^{N} a_{n} \geq k a_{1}$
The base case, $k=1$ and $N=1$ , is trivial. Given that (1) is true for a given $k$ , we have
$k a_{1} \leq \sum_{n=1}^{N} a_{n} \leq \sum_{n=1}^{N}\left(a_{2 n}+a_{2 n+1}\right)=\sum_{\substack{2 \leq n \leq 2 N \\ n \text{ even }}} a_{n}+\sum_{\substack{3 \leq n \leq 2 N+1 \\ n \text{ odd }}} a_{n}=\sum_{n=2}^{2 N+1} a_{n}$
Adding $a_{1}$ , we get
$\sum_{n=1}^{2 N+1} a_{n} \geq(k+1) a_{1}$
as desired.

The problem now follows by taking $k$ large enough so that $k>1 / a_{1}$ , so $k a_{1}>1$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.