Maths Olympiad Prep

Library / /32 of 462

Algebra Difficulty 4.6 AIME Prove it Ireland

Suppose 0x<10 \le x < 1 and let an=1xnn(1x)a_n = \frac{1-x^n}{n(1-x)} for all integers n1n \ge 1. Prove that
an+1an1n+1,n=1,2,3, |a_{n+1} - a_n| \le \frac{1}{n+1}, \quad n = 1, 2, 3, \dots

Solution

First of all, note that an=1n(1+x++xn1)a_n = \frac{1}{n}(1 + x + \cdots + x^{n-1}), hence
an+1an=n(1+x++xn)(n+1)(1+x++xn1)n(n+1)=1n(n+1)(nxnk=0n1xk)=1n(n+1)k=0n1(xnxk). \begin{align*} a_{n+1} - a_n &= \frac{n(1 + x + \cdots + x^n) - (n+1)(1 + x + \cdots + x^{n-1})}{n(n+1)} \\ &= \frac{1}{n(n+1)} \left( n x^n - \sum_{k=0}^{n-1} x^k \right) \\ &= \frac{1}{n(n+1)} \sum_{k=0}^{n-1} (x^n - x^k). \end{align*}

Since 0x<10 \le x < 1, for i0i \ge 0 we have 0xi10 \le x^i \le 1, hence 0xnxk10 \le |x^n - x^k| \le 1 for k=0,1,,n1k = 0, 1, \dots, n-1, and so

an+1an=1n(n+1)k=0n1(xnxk)1n(n+1)k=0n1xnxknn(n+1)=1n+1.\begin{aligned} |a_{n+1} - a_n| &= \frac{1}{n(n+1)} \left| \sum_{k=0}^{n-1} (x^n - x^k) \right| \\ &\le \frac{1}{n(n+1)} \sum_{k=0}^{n-1} |x^n - x^k| \le \frac{n}{n(n+1)} = \frac{1}{n+1}. \end{aligned}

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.