Task 2. Determine the largest real number $M$ such that for every infinite sequence $x_{0}, x_{1}, x_{2}, \ldots$ of real numbers that satisfies
a) $x_{0}=1$ and $x_{1}=3$,
b) $x_{0}+x_{1}+\cdots+x_{n-1} \geq 3 x_{n}-x_{n+1}$,

it holds that

$$
\frac{x_{n+1}}{x_{n}}>M
$$

for all $n \geq 0$.
Solution. Answer: the largest possible constant for which this holds is $M=2$.

This problem is a typical example where it is beneficial to take a stronger induction hypothesis than strictly necessary: we show by induction that $x_{n+1}>2 x_{n}>x_{n}+x_{n-1}+\ldots+x_{0}$. For $n=0$, this translates to $x_{1}>2 x_{0}>x_{0}$, which, with the given initial values, becomes $3>2>1$. Now assume as the induction hypothesis that $x_{n+1}>2 x_{n}>x_{n}+x_{n-1}+\ldots+x_{0}$. Then for $x_{n+2}$, using the given condition, we have

$$
\begin{aligned}
x_{n+2} & \geq 3 x_{n+1}-\left(x_{n}+\ldots+x_{0}\right) \\
& >2 x_{n+1} \\
& >x_{n+1}+x_{n}+\ldots+x_{0} .
\end{aligned}
$$

This completes the induction step. From this, it follows that for all possible sequences and all possible $n$, $\frac{x_{n+1}}{x_{n}}>2$.

To show that we cannot find a higher value for $M$, consider the sequence for which equality holds in b), i.e., $x_{0}+x_{1}+\cdots+x_{n-1}=3 x_{n}-x_{n+1}$. Then we have

$$
\begin{aligned}
x_{n+1} & =3 x_{n}-\left(x_{n-1}+\ldots+x_{0}\right) \\
& =3 x_{n}-x_{n-1}-\left(x_{n-2}+\ldots+x_{0}\right) \\
& =3 x_{n}-x_{n-1}-\left(3 x_{n-1}-x_{n}\right) \\
& =4 x_{n}-4 x_{n-1} .
\end{aligned}
$$

The characteristic equation of this homogeneous recurrence relation is $\lambda^{2}-4 \lambda+4=(\lambda-2)^{2}=0$. Since this has a double root at $\lambda=2$, the two characteristic solutions are $2^{n}$ and $n 2^{n}$. Solving $x_{n}=B 2^{n}+C n 2^{n}$ for the given initial values, we get $B+0=x_{0}=1$ and $2 B+2 C=x_{1}=3$, so $B=1$ and $C=\frac{1}{2}$. The solution for these initial values is thus $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, we simply calculate that

$$
\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)
$$

For large $n$, this fraction approaches 2 arbitrarily closely. To make this precise: 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, such an $M$ does not satisfy the condition. The largest value of $M$ that can satisfy the condition is thus 2, and we have shown above that this value does indeed satisfy the condition.