IMC 1996 · Day 1 · P4

(i) We show by induction that $$\tag{$*$} a_n \le q^n \quad \text{for } n \ge 3,$$ where $q = 0.7$ and use that $0.7 < 2^{-1/2}$. One has $a_1 = 1$, $a_2 = \frac{1}{2}$, $a_3 = \frac{1}{3}$, $a_4 = \frac{11}{48}$. Therefore ($*$) is true for $n = 3$ and $n = 4$. Assume ($*$) is true for $n \le N - 1$ for some $N \ge 5$. Then $$a_N = \frac{2}{N} a_{N-1} + \frac{1}{N} a_{N-2} + \frac{1}{N} \sum_{k=3}^{N-3} a_k a_{N-k} \le \frac{2}{N} q^{N-1} + \frac{1}{N} q^{N-2} + \frac{N-5}{N} q^N \le q^N$$ because $\dfrac{2}{q} + \dfrac{1}{q^2} \le 5$.

(ii) We show by induction that $$a_n \ge q^n \quad \text{for } n \ge 2,$$ where $q = \dfrac{2}{3}$. One has $a_2 = \dfrac{1}{2} > \left( \dfrac{2}{3} \right)^2 = q^2$. Going by induction we have for $N \ge 3$ $$a_N = \frac{2}{N} a_{N-1} + \frac{1}{N} \sum_{k=2}^{N-2} a_k a_{N-k} \ge \frac{2}{N} q^{N-1} + \frac{N-3}{N} q^N = q^N$$ because $\dfrac{2}{q} = 3$.