IMO Team Selection Test 1

The largest possible $M$ for which the given property holds is $M=2$.

We first show that the given property holds for $M=2$. To do this, we show by induction on $n$ the stronger statement that $x_{n+1}>2x_n>x_n+x_{n-1}+\cdots +x_0$ for all $n\ge 0$.

For $n=0$, this is the statement $x_1>2x_0>x_0$ which translates with the given initial values to $3>2>1$.

Now suppose for the induction hypothesis that $x_{n+1}>2x_n>x_n+x_{n-1}+\cdots +x_0$. Then we find for $x_{n+2}$: $$\begin{array}{rl}{x}_{n+2}& \ge 3x_{n+1}-(x_n+\cdots +x_0)\\ & >2x_{n+1}\\ & >x_{n+1}+x_n+\cdots +x_0.\end{array}$$ This completes the induction step. By induction, it follows that for all sequences $x$ satisfying (a) and (b), the inequality $\frac{x_{n+1}}{x_n}>2$ holds for all $n\ge 0$.

To show that we cannot find a higher value for $M$, we look at the sequence $x$ with $x_0=1$, $x_1=3$, and for which equality holds in (b), i.e. $x_0+x_1+\cdots +x_{n-1}=3x_n-x_{n+1}$ for all $n\ge 1$. Then the following relation holds: $$\begin{array}{rl}{x}_{n+1}& =3x_n-(x_{n-1}+\cdots +x_0)\\ & =3x_n-x_{n-1}-(x_{n-2}+\cdots +x_0)\\ & =3x_n-x_{n-1}-(3x_{n-1}-x_n)\\ & =4x_n-4x_{n-1}.\end{array}$$ Note that this is a homogeneous linear recurrence relation, the characteristic equation of which is ${\lambda }^2-4\lambda +4=(\lambda -2{)}^2=0$. Since the characteristic equation has a double root at $\lambda =2$, the general solution of the recurrence relation is of the form $x_n=B{2}^n+Cn{2}^n$ for real numbers $B$ and $C$.

If we now solve this for the given starting values $x_0=1$ and $x_1=3$, we get the system of equations $B+0=x_0=1$ and $2B+2C=x_1=3$. Its unique solution is given by $B=1$ and $C=\frac{1}{2}$. So the solution for these starting values is $x_n=1\cdot 2^n+\frac{1}{2}n{2}^n=(n+2)2^{n-1}$.

Now that we have solved the recurrence relation, a simple computation yields $$\frac{x_{n+1}}{x_n}=\frac{(n+3)2^n}{(n+2)2^{n-1}}=2\frac{n+3}{n+2}=2\left(1+\frac{1}{n+2}\right).$$ So for sufficiently large $n$, this fraction becomes arbitrarily close to 2. To state this more precisely: suppose $M=2+\epsilon$ with $\epsilon >0$. Then, for this sequence and $n>\frac{2}{\epsilon }-2$, we have $\frac{x_{n+1}}{x_n}=2+\frac{2}{n+2}<2+\epsilon =M$. Therefore no such $M$ can have the given property.

So the largest value of $M$ that has the given property is 2, and in the first part of this solution we have already seen that $M=2$ has the given property. $\square$