AlgebraDifficulty 7.5National olympiad, round 2Prove it
Let (xn)n=1∞ be a sequence defined recursively with: x1=2 and xn+1=n+1xn(xn+n) for all n≥1. Prove that n(n+1)>xn+1(x1+x2+…+xn)2.
Proposed by Nikola Velov
Solution
1. Define the sequence and the sum: Let (xn)n=1∞ be a sequence defined recursively by: x1=2andxn+1=n+1xn(xn+n)for alln≥1. Define Sn=x1+x2+…+xn.
2. State the inequality to prove: We need to prove that: n(n+1)>xn+1(x1+x2+…+xn)2. This can be rewritten using Sn as: Sn<n(n+1)xn+1.
3. Base case: For n=1: S1=x1=2andx2=2x1(x1+1)=22⋅3=3. We need to check: 2<1⋅2⋅3=6. Since 2<6, the base case holds.
4. Inductive step: Assume the inequality holds for some n≥1, i.e., Sn<n(n+1)xn+1. We need to show that: Sn+1<(n+1)(n+2)xn+2. Note that: Sn+1=Sn+xn+1. By the inductive hypothesis: Sn+1=Sn+xn+1<n(n+1)xn+1+xn+1.
5. Simplify the inequality: We need to prove: n(n+1)xn+1+xn+1<(n+1)(n+2)xn+2. Using the recursive definition: (n+2)xn+2=xn+1(xn+1+n+1). Thus, we need to show: n(n+1)xn+1+xn+1<(n+1)xn+1(xn+1+n+1).
6. Algebraic manipulation: Square both sides to eliminate the square roots: (n(n+1)xn+1+xn+1)2<(n+1)xn+1(xn+1+n+1). Expanding both sides: n(n+1)xn+1+2xn+1n(n+1)xn+1+xn+12<(n+1)xn+12+(n+1)xn+1(n+1). Simplify: n(n+1)xn+1+2xn+1n(n+1)xn+1+xn+12<(n+1)xn+12+(n+1)2xn+1. Combine like terms: 2xn+1n(n+1)xn+1<(n+1)2xn+1−n(n+1)xn+1. Factor out xn+1: 2n(n+1)xn+1<(n+1)xn+1+(n+1)xn+1. Simplify: 2n(n+1)xn+1<(2n+1)xn+1. Divide both sides by xn+1: 2n(n+1)<2n+1. This is immediate from the AM-GM inequality and the fact that 2n+1>n+1.
Thus, the inequality holds for all n≥1 by induction.
■
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: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.