49th International Mathematical Olympiad Spain

Since $a_i\ge \gcd \left(a_i,a_{i+1}\right)>a_{i-1}$, the sequence is strictly increasing. In particular $a_0\ge 1,a_1\ge 2$. For each $i\ge 1$ we also have $a_{i+1}-a_i\ge \gcd \left(a_i,a_{i+1}\right)>a_{i-1}$, and consequently $a_{i+1}\ge a_i+a_{i-1}+1$. Hence $a_2\ge 4$ and $a_3\ge 7$. The equality $a_3=7$ would force equalities in the previous estimates, leading to $\gcd \left(a_2,a_3\right)=\gcd (4,7)>a_1=2$, which is false. Thus $a_3\ge 8$; the result is valid for $n=0,1,2,3$. These are the base cases for a proof by induction.

Take an $n\ge 3$ and assume that $a_i\ge 2^i$ for $i=0,1,\dots ,n$. We must show that $a_{n+1}\ge 2^{n+1}$. Let $\gcd \left(a_n,a_{n+1}\right)=d$. We know that $d>a_{n-1}$. The induction claim is reached immediately in the following cases: $$\begin{array}{rl}& \text{ if }{a}_{n+1}\ge 4d\text{ then }{a}_{n+1}>4a_{n-1}\ge 4\cdot 2^{n-1}=2^{n+1};\\ & \text{ if }{a}_n\ge 3d\text{ then }{a}_{n+1}\ge a_n+d\ge 4d>4a_{n-1}\ge 4\cdot 2^{n-1}=2^{n+1};\\ & \text{ if }{a}_n=d\text{ then }{a}_{n+1}\ge a_n+d=2a_n\ge 2\cdot 2^n=2^{n+1}.\end{array}$$ The only remaining possibility is that $a_n=2d$ and $a_{n+1}=3d$, which we assume for the sequel. So $a_{n+1}=\frac{3}{2}{a}_n$.

Let now $\gcd \left(a_{n-1},a_n\right)=d^{\prime }$; then $d^{\prime }>a_{n-2}$. Write $a_n=m{d}^{\prime }$ ( $m$ an integer). Keeping in mind that $d^{\prime }\le a_{n-1}<d$ and $a_n=2d$, we get that $m\ge 3$. Also $a_{n-1}<d=\frac{1}{2}m{d}^{\prime }$, $a_{n+1}=\frac{3}{2}m{d}^{\prime }$. Again we single out the cases which imply the induction claim immediately: $$\begin{array}{rl}& \text{ if }m\ge 6\text{ then }{a}_{n+1}=\frac{3}{2}m{d}^{\prime }\ge 9d^{\prime }>9a_{n-2}\ge 9\cdot 2^{n-2}>2^{n+1};\\ & \text{ if }3\le m\le 4\text{ then }{a}_{n-1}<\frac{1}{2}\cdot 4d^{\prime },\text{ and hence }{a}_{n-1}=d^{\prime },\\ & a_{n+1}=\frac{3}{2}m{a}_{n-1}\ge \frac{3}{2}\cdot 3a_{n-1}\ge \frac{9}{2}\cdot 2^{n-1}>2^{n+1}.\end{array}$$ So we are left with the case $m=5$, which means that $a_n=5d^{\prime },a_{n+1}=\frac{15}{2}{d}^{\prime },a_{n-1}<d=\frac{5}{2}{d}^{\prime }$. The last relation implies that $a_{n-1}$ is either $d^{\prime }$ or $2d^{\prime }$. Anyway, $a_{n-1}\mid 2d^{\prime }$.

The same pattern repeats once more. We denote $\gcd \left(a_{n-2},a_{n-1}\right)=d^{\prime \prime }$; then $d^{\prime \prime }>a_{n-3}$. Because $d^{\prime \prime }$ is a divisor of $a_{n-1}$, hence also of $2d^{\prime }$, we may write $2d^{\prime }=m^{\prime }{d}^{\prime \prime }$ ( $m^{\prime }$ an integer). Since $d^{\prime \prime }\le a_{n-2}<d^{\prime }$, we get $m^{\prime }\ge 3$. Also, $a_{n-2}<d^{\prime }=\frac{1}{2}{m}^{\prime }{d}^{\prime \prime },a_{n+1}=\frac{15}{2}{d}^{\prime }=\frac{15}{4}{m}^{\prime }{d}^{\prime \prime }$. As before, we consider the cases: $$\begin{array}{rl}& \text{ if }{m}^{\prime }\ge 5\text{ then }{a}_{n+1}=\frac{15}{4}{m}^{\prime }{d}^{\prime \prime }\ge \frac{75}{4}{d}^{\prime \prime }>\frac{75}{4}{a}_{n-3}\ge \frac{75}{4}\cdot 2^{n-3}>2^{n+1};\\ & \text{ if }3\le m^{\prime }\le 4\text{ then }{a}_{n-2}<\frac{1}{2}\cdot 4d^{\prime \prime },\text{ and hence }{a}_{n-2}=d^{\prime \prime },\\ & a_{n+1}=\frac{15}{4}{m}^{\prime }{a}_{n-2}\ge \frac{15}{4}\cdot 3a_{n-2}\ge \frac{45}{4}\cdot 2^{n-2}>2^{n+1}.\end{array}$$ Both of them have produced the induction claim. But now there are no cases left. Induction is complete; the inequality $a_n\ge 2^n$ holds for all $n$.