Maths Olympiad Prep

Library / /1 of 55

, 2006

Algebra Difficulty 7.5 National olympiad, round 2 Prove it IMO

The sequence of real numbers a0,a1,a2,a_{0}, a_{1}, a_{2}, \ldots is defined recursively by
a0=1,k=0nankk+1=0 for n1 a_{0}=-1, \quad \sum_{k=0}^{n} \frac{a_{n-k}}{k+1}=0 \quad \text{ for } \quad n \geq 1
Show that an>0a_{n}>0 for n1n \geq 1.

Solution

The proof goes by induction. For n=1n=1 the formula yields a1=1/2a_{1}=1 / 2. Take n1n \geq 1, assume a1,,an>0a_{1}, \ldots, a_{n}>0 and write the recurrence formula for nn and n+1n+1, respectively as
k=0naknk+1=0 and k=0n+1aknk+2=0. \sum_{k=0}^{n} \frac{a_{k}}{n-k+1}=0 \quad \text{ and } \quad \sum_{k=0}^{n+1} \frac{a_{k}}{n-k+2}=0 .
Subtraction yields
0=(n+2)k=0n+1aknk+2(n+1)k=0naknk+1=(n+2)an+1+k=0n(n+2nk+2n+1nk+1)ak \begin{aligned} 0=(n+2) \sum_{k=0}^{n+1} & \frac{a_{k}}{n-k+2}-(n+1) \sum_{k=0}^{n} \frac{a_{k}}{n-k+1} \\ & =(n+2) a_{n+1}+\sum_{k=0}^{n}\left(\frac{n+2}{n-k+2}-\frac{n+1}{n-k+1}\right) a_{k} \end{aligned}
The coefficient of a0a_{0} vanishes, so
an+1=1n+2k=1n(n+1nk+1n+2nk+2)ak=1n+2k=1nk(nk+1)(nk+2)ak. a_{n+1}=\frac{1}{n+2} \sum_{k=1}^{n}\left(\frac{n+1}{n-k+1}-\frac{n+2}{n-k+2}\right) a_{k}=\frac{1}{n+2} \sum_{k=1}^{n} \frac{k}{(n-k+1)(n-k+2)} a_{k} .
The coefficients of a1,,ana_{1}, \ldots, a_{n} are all positive. Therefore, a1,,an>0a_{1}, \ldots, a_{n}>0 implies an+1>0a_{n+1}>0.

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.