Let $a$ be a positive real number and $\{x_n\}_{n\geq 1}$ a sequence of real numbers such that $x_1=a$ and \[ x_{n+1} \geq (n+2)x_n - \sum^{n-1}_{k=1}kx_k, \ \forall \ n\geq 1. \] Prove that there exists a positive integer $n$ such that $x_n > 1999!$. Ciprian Manolescu
Problem
Source: Romanian IMO Team Selection Test TST 1999, problem 8
Tags: induction, algebra proposed, algebra
25.09.2005 00:56
Let $S_n=\sum_{k=1}^nkx_k$. We want to show that $x_n\ge S_{n-1}$ for all $n$. This is trivially true for $n=1$. Assuming $x_n\ge S_{n-1}$, we have $x_{n+1}\ge nx_n+2S_{n-1}-S_{n-1}=nx_n+S_{n-1}=S_n$. In particular, $x_n\ge (n-1)x_{n-1}$ and hence $x_n>(n-1)!a$, so $x_n$ is unbounded and we are done.
21.02.2010 12:10
Official Solution. We will prove by induction that \[ x_{n+1}>\sum_{k=1}^{n}kx_k.\] For $ n=1$, the definition gives $ x_2\geq 3x_1>x_1$. Suppose $ x_{n+1}>\sum_{k=1}^{n}kx_k$ and we shall prove the corresponding formula for $ x_{n+2}$, \begin{eqnarray*} x_{n+2}\geq (n+3)x_{n+1}-\sum_{k=1}^{n}kx_k&=&(n+1)x_{n+1}+2x_{n+1}-\sum_{k=1}^{n}kx_k\\ &>&(n+1)x_{n+1}+2\sum_{k=1}^{n}kx_k-\sum_{k=1}^{n}kx_k=(n+1)x_{n+1}+\sum_{k=1}^{n}kx_k=\sum_{k=1}^{n+1}kx_k. \end{eqnarray*} From this we deduce, \[ x_{n+1}>\sum_{k=1}^{n}kx_k>nx_n.\] By induction, \[ x_{n+1}>nx_n>n(n-1)x_{n-1}>\cdots >n!a.\] Obviously, for sufficiently large $ n$, we have $ n!a>1999!$.
08.10.2014 13:36
Here my solution: We will prove that $ x_{n+1} \ge 3 x_n $ by induction on $ n $.Suppose that $ x_{j+1} \ge 3 x_j $ is true for $ j \le n-1 $.Then ( by condtion of the problem) $ \frac{x_{n+1}}{x_n} \ge (n+2) - (\frac{x_1}{x_n}+\frac{2x_2}{x_n} + ... + \frac{(n-1)x_{n-1}}{x_n}) \ge (n+2)-(n-1)(\frac{1}{3}+\frac{1}{9}+...)=\frac{n+5}{2} \ge 3 $, so claim is proven.Hence we can take $ n $ such that $ n>1+log_3 (\frac{1999!}{a}) $ : $ x_n \ge 3^{n-1}x_1=3^{n-1}a>1999! $.DONE !