Maths Olympiad Prep

Library / /62 of 94

Algebra Difficulty 6.5 National Olympiad Prove it Hong Kong

Let a1,a2,a3,a_1, a_2, a_3, \dots be a sequence of positive numbers. If there exists a positive number MM such that for every n=1,2,3,n = 1, 2, 3, \dots,
a12+a22++an2<Man+12, a_1^2 + a_2^2 + \dots + a_n^2 < M a_{n+1}^2,
then prove that there exists a positive number MM' such that for every n=1,2,3,n = 1, 2, 3, \dots,
a1+a2++an<Man+1. a_1 + a_2 + \dots + a_n < M' a_{n+1}.

Solution

We say that a sequence {bn}\{b_n\} of positive real numbers is good if there exists a positive constant NN such that
b1+b2++bn<Nbn+1(1) b_1 + b_2 + \cdots + b_n < N b_{n+1} \quad (1)
for any nZ+n \in \mathbb{Z}^+.
We first prove the following equivalent conditions for a sequence to be good.

Claim. A sequence {bn}\{b_n\} of positive real numbers is good if and only if the following conditions hold.
(i) There exists a constant r>0r > 0 such that bn+1>rbnb_{n+1} > r b_n for any nZ+n \in \mathbb{Z}^+; and
(ii) there exists a positive integer dd such that bn+d>2bnb_{n+d} > 2 b_n for any nZ+n \in \mathbb{Z}^+.

Proof. Suppose {bn}\{b_n\} is good. Then we have Nbn+1>bnN b_{n+1} > b_n. So we can take r=1Nr = \frac{1}{N} for (i). Next, we take dd to be any integer larger than 2N2+12N^2 + 1. Note that Nbn+j>b1+b2++bn+j1>bnN b_{n+j} > b_1 + b_2 + \cdots + b_{n+j-1} > b_n for any jZ+j \in \mathbb{Z}^+. It follows that
bn+d>1N(b1+b2++bn+d1)>1N(bn+1+bn+2++bn+d1)>1N2(bn+bn+1++bn)=d1N2bn>2bn. \begin{aligned} b_{n+d} &> \frac{1}{N}(b_1 + b_2 + \cdots + b_{n+d-1}) \\ &> \frac{1}{N}(b_{n+1} + b_{n+2} + \cdots + b_{n+d-1}) \\ &> \frac{1}{N^2}(b_n + b_{n+1} + \cdots + b_n) \\ &= \frac{d-1}{N^2} b_n \\ &> 2 b_n. \end{aligned}
This proves (ii).

Conversely, suppose (i) and (ii) hold. For any nZ+n \in \mathbb{Z}^+, we have
b1+b2++bn=j=1d(bn+1j+bn+1jd+bn+1j2d+)<j=1d(bn+1j+12bn+1j+122bn+1j+)<j=1d2bn+1j<2(j=1d1rj)bn+1. \begin{aligned} b_1 + b_2 + \cdots + b_n &= \sum_{j=1}^{d} (b_{n+1-j} + b_{n+1-j-d} + b_{n+1-j-2d} + \cdots) \\ &< \sum_{j=1}^{d} \left( b_{n+1-j} + \frac{1}{2} b_{n+1-j} + \frac{1}{2^2} b_{n+1-j} + \cdots \right) \\ &< \sum_{j=1}^{d} 2 b_{n+1-j} \\ &< 2 \left( \sum_{j=1}^{d} \frac{1}{r^j} \right) b_{n+1}. \end{aligned}
So we can take N=2(j=1d1rj)N = 2 \left( \sum_{j=1}^{d} \frac{1}{r^j} \right) so that (1) holds. \square

We go back to the original problem. Note that the sequence {an2}\{a_n^2\} is good by the given condition. By the claim, there exists r>0r > 0 and dZ+d \in \mathbb{Z}^+ such that an+12>ran2a_{n+1}^2 > r a_n^2 and an+d2>2an2a_{n+d}^2 > 2 a_n^2 for any nZ+n \in \mathbb{Z}^+. This implies an+1>rana_{n+1} > \sqrt{r} a_n and
an+2d>2an+d>2an. a_{n+2d} > \sqrt{2} a_{n+d} > 2 a_n.
Therefore, the sequence {an}\{a_n\} is good by the claim. This is exactly our goal.

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.