Maths Olympiad Prep

Library / /40 of 100

Algebra Difficulty 4.7 AIME Prove it China

Suppose positive number sequence {xn}\{x_n\} satisfies Sn2Sn1S_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
xnC2n, n=1,2, x_n \ge C \cdot 2^n,\ n = 1, 2, \dots

Solution

When n2n \ge 2, Sn2Sn1S_n \ge 2S_{n-1} is equivalent to
xnx1++xn1. x_n \ge x_1 + \cdots + x_{n-1}. \qquad ①
Let C=14x1C = \frac{1}{4}x_1. We will prove
xnC2n, 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 x2x1=C22x_2 \ge x_1 = C \cdot 2^2.

When n3n \ge 3, assume xkC2kx_k \ge C \cdot 2^k, k=1,2,,n1k = 1, 2, \dots, n-1.
Then from ①, we have
xnx1+(x2++xn1)x1+(C22++C2n1)=C(22+22+23++2n1)=C2n. \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.