Maths Olympiad Prep

Library / China Mathematical Competition /52 of 136

China Mathematical Competition

Algebra Difficulty 4.7 AIME Prove it China

Suppose positive number sequence {xn}\{x_n\} satisfies Sn≥2Sn−1S_n \ge 2S_{n-1}, n=2,3,…n = 2, 3, \dots, where Sn=x1+⋯+xnS_n = x_1 + \dots + x_n. Prove that there exists a constant C>0C > 0, such that
xn≥C⋅2n, n=1,2,… x_n \ge C \cdot 2^n,\ n = 1, 2, \dots

Solution

When n≥2n \ge 2, Sn≥2Sn−1S_n \ge 2S_{n-1} is equivalent to
xn≥x1+⋯+xn−1.① x_n \ge x_1 + \cdots + x_{n-1}. \qquad ①
Let C=14x1C = \frac{1}{4}x_1. We will prove
xn≥C⋅2n, n=1,2,…2◯ x_n \ge C \cdot 2^n,\ n = 1, 2, \dots \qquad \textcircled{2}
by induction.

When n=1n = 1, it is obviously true. When n=2n = 2, we have x2≥x1=C⋅22x_2 \ge x_1 = C \cdot 2^2.

When n≥3n \ge 3, assume xk≥C⋅2kx_k \ge C \cdot 2^k, k=1,2,…,n−1k = 1, 2, \dots, n-1.
Then from ①, we have
xn≥x1+(x2+⋯+xn−1)≥x1+(C⋅22+⋯+C⋅2n−1)=C(22+22+23+⋯+2n−1)=C⋅2n. \begin{align*} x_n &\ge x_1 + (x_2 + \cdots + x_{n-1}) \\ &\ge x_1 + (C \cdot 2^2 + \cdots + C \cdot 2^{n-1}) \\ &= C(2^2 + 2^2 + 2^3 + \cdots + 2^{n-1}) = C \cdot 2^n. \end{align*}
Therefore, ② holds for every nn.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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