Maths Olympiad Prep

Library / /7 of 18

Algebra Difficulty 4.8 AIME Prove it United States

Problem:
Let a1,a2,a3,a_{1}, a_{2}, a_{3}, \ldots be an infinite sequence of positive real numbers such that for all n1n \geq 1,
ana2n+a2n+1 a_{n} \leq a_{2 n}+a_{2 n+1}
Prove that there exists an N1N \geq 1 such that
n=1Nan>1 \sum_{n=1}^{N} a_{n}>1

Solution

Solution:
Let us prove by induction that for any positive integer kk, there is an NN for which
n=1Nanka1 \sum_{n=1}^{N} a_{n} \geq k a_{1}
The base case, k=1k=1 and N=1N=1, is trivial. Given that (1) is true for a given kk, we have
ka1n=1Nann=1N(a2n+a2n+1)=2n2Nn even an+3n2N+1n odd an=n=22N+1an 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 a1a_{1}, we get
n=12N+1an(k+1)a1 \sum_{n=1}^{2 N+1} a_{n} \geq(k+1) a_{1}
as desired.

The problem now follows by taking kk large enough so that k>1/a1k>1 / a_{1}, so ka1>1k a_{1}>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.