2006 IMO Shortlist Problems/A2


(Poland) The sequence of real number $a_0, a_1, a_2, \dots$ is defined recursively by

$\displaystyle a_0 = -1$, $\sum_{k=0}^n \frac{a_{n-k}}{k+1} = 0$ for $n \ge 1$.

Show that $\displaystyle {} a_n > 0$ for $n \ge 1$.

This was also Problem 6 of the 2007 Poland Math Olympiad.


We proceed by induction on $\displaystyle n$. For the base case, we note that $\displaystyle a_1 = 1/2$. Suppose that $a_1, \dots, a_{n-1}$ are positive. We note that $\displaystyle a_n$ is positive if and only if $\sum_{k=1}^n \frac{a_{n-k}}{k+1}$ is negative. Now, since $a_1, \dots, a_{n-1}$ are all positive, we know

${} - \frac{a_0}{n+1} = \frac{n}{n+1} \cdot \left( -\frac{a_0}{n} \right) = \frac{n}{n+1} \sum_{k=0}^{n-2}\frac{a_{n-1-k}}{k+1} > \sum_{k=0}^{n-2} \frac{k+1}{k+2} \cdot \frac{a_{n-1-k}}{k+1} = \sum_{k=0}^{n-2} \frac{a_{n-1-k}}{k+2}$ .

This means that

$\sum_{k=1}^{n} = \frac{a_0}{n+1} + \sum_{k=1}^{n-1} \frac{a_{n-k}}{k+1} = \frac{a_0}{n+1} + \sum_{k=0}^{n-2}\frac{a_{n-1-k}}{k+2} < \frac{a_0}{n+1} - \frac{a_0}{n+1} = 0$,

as desired.