International Mathematical Olympiad

The value of $b_{0}$ is irrelevant since $a_{0}=0$, so we may assume that $b_{0}=1$.

Lemma. We have $a_{n} \geqslant 1$ for all $n \geqslant 1$.

Proof. Let us suppose otherwise in order to obtain a contradiction. Let
$$\begin{equation*} n \geqslant 1 \text{ be the smallest integer with } a_{n} \leqslant 0 \text{. } \tag{1} \end{equation*}$$
Note that $n \geqslant 2$. It follows that $a_{n-1} \geqslant 1$ and $a_{n-2} \geqslant 0$. Thus we cannot have $a_{n}= a_{n-1} b_{n-1}+a_{n-2}$, so we must have $a_{n}=a_{n-1} b_{n-1}-a_{n-2}$. Since $a_{n} \leqslant 0$, we have $a_{n-1} \leqslant a_{n-2}$. Thus we have $a_{n-2} \geqslant a_{n-1} \geqslant a_{n}$.

Let
$$\begin{equation*} r \text{ be the smallest index with } a_{r} \geqslant a_{r+1} \geqslant a_{r+2} \text{. } \tag{2} \end{equation*}$$
Then $r \leqslant n-2$ by the above, but also $r \geqslant 2$ : if $b_{1}=1$, then $a_{2}=a_{1}=1$ and $a_{3}=a_{2} b_{2}+a_{1}>a_{2}$; if $b_{1}>1$, then $a_{2}=b_{1}>1=a_{1}$.

By the minimal choice (2) of $r$, it follows that $a_{r-1}<a_{r}$. And since $2 \leqslant r \leqslant n-2$, by the minimal choice (1) of $n$ we have $a_{r-1}, a_{r}, a_{r+1}>0$. In order to have $a_{r+1} \geqslant a_{r+2}$, we must have $a_{r+2}=a_{r+1} b_{r+1}-a_{r}$ so that $b_{r} \geqslant 2$. Putting everything together, we conclude that
$$a_{r+1}=a_{r} b_{r} \pm a_{r-1} \geqslant 2 a_{r}-a_{r-1}=a_{r}+\left(a_{r}-a_{r-1}\right)>a_{r},$$
which contradicts (2). $\square$

To complete the problem, we prove that $\max \left\{a_{n}, a_{n+1}\right\} \geqslant n$ by induction. The cases $n=0,1$ are given. Assume it is true for all non-negative integers strictly less than $n$, where $n \geqslant 2$. There are two cases:

Case 1: $b_{n-1}=1$.

Then $a_{n+1}=a_{n} b_{n}+a_{n-1}$. By the inductive assumption one of $a_{n-1}, a_{n}$ is at least $n-1$ and the other, by the lemma, is at least 1. Hence
$$a_{n+1}=a_{n} b_{n}+a_{n-1} \geqslant a_{n}+a_{n-1} \geqslant(n-1)+1=n .$$
Thus $\max \left\{a_{n}, a_{n+1}\right\} \geqslant n$, as desired.

Case 2: $b_{n-1}>1$.

Since we defined $b_{0}=1$ there is an index $r$ with $1 \leqslant r \leqslant n-1$ such that
$$b_{n-1}, b_{n-2}, \ldots, b_{r} \geqslant 2 \quad \text{ and } \quad b_{r-1}=1 .$$
We have $a_{r+1}=a_{r} b_{r}+a_{r-1} \geqslant 2 a_{r}+a_{r-1}$. Thus $a_{r+1}-a_{r} \geqslant a_{r}+a_{r-1}$.

Now we claim that $a_{r}+a_{r-1} \geqslant r$. Indeed, this holds by inspection for $r=1$; for $r \geqslant 2$, one of $a_{r}, a_{r-1}$ is at least $r-1$ by the inductive assumption, while the other, by the lemma, is at least 1. Hence $a_{r}+a_{r-1} \geqslant r$, as claimed, and therefore $a_{r+1}-a_{r} \geqslant r$ by the last inequality in the previous paragraph.

Since $r \geqslant 1$ and, by the lemma, $a_{r} \geqslant 1$, from $a_{r+1}-a_{r} \geqslant r$ we get the following two inequalities:
$$a_{r+1} \geqslant r+1 \quad \text{ and } \quad a_{r+1}>a_{r} .$$
Now observe that
$$a_{m}>a_{m-1} \Longrightarrow a_{m+1}>a_{m} \text{ for } m=r+1, r+2, \ldots, n-1 \text{, }$$
since $a_{m+1}=a_{m} b_{m}-a_{m-1} \geqslant 2 a_{m}-a_{m-1}=a_{m}+\left(a_{m}-a_{m-1}\right)>a_{m}$. Thus
$$a_{n}>a_{n-1}>\cdots>a_{r+1} \geqslant r+1 \Longrightarrow a_{n} \geqslant n$$
So $\max \left\{a_{n}, a_{n+1}\right\} \geqslant n$, as desired.

We say that an index $n>1$ is bad if $b_{n-1}=1$ and $b_{n-2}>1$; otherwise $n$ is good. The value of $b_{0}$ is irrelevant to the definition of $\left(a_{n}\right)$ since $a_{0}=0$; so we assume that $b_{0}>1$.

Lemma 1. (a) $a_{n} \geqslant 1$ for all $n>0$.
(b) If $n>1$ is good, then $a_{n}>a_{n-1}$.

Proof. Induction on $n$. In the base cases $n=1,2$ we have $a_{1}=1 \geqslant 1, a_{2}=b_{1} a_{1} \geqslant 1$, and finally $a_{2}>a_{1}$ if 2 is good, since in this case $b_{1}>1$.

Now we assume that the lemma statement is proved for $n=1,2, \ldots, k$ with $k \geqslant 2$, and prove it for $n=k+1$. Recall that $a_{k}$ and $a_{k-1}$ are positive by the induction hypothesis.

Case 1: $k$ is bad.
We have $b_{k-1}=1$, so $a_{k+1}=b_{k} a_{k}+a_{k-1} \geqslant a_{k}+a_{k-1}>a_{k} \geqslant 1$, as required.

Case 2: $k$ is good.
We already have $a_{k}>a_{k-1} \geqslant 1$ by the induction hypothesis. We consider three easy subcases.

Subcase 2.1: $b_{k}>1$.
Then $a_{k+1} \geqslant b_{k} a_{k}-a_{k-1} \geqslant a_{k}+\left(a_{k}-a_{k-1}\right)>a_{k} \geqslant 1$.

Subcase 2.2: $b_{k}=b_{k-1}=1$.
Then $a_{k+1}=a_{k}+a_{k-1}>a_{k} \geqslant 1$.

Subcase 2.3: $b_{k}=1$ but $b_{k-1}>1$.
Then $k+1$ is bad, and we need to prove only (a), which is trivial: $a_{k+1}=a_{k}-a_{k-1} \geqslant 1$.

So, in all three subcases we have verified the required relations.

Lemma 2. Assume that $n>1$ is bad. Then there exists a $j \in\{1,2,3\}$ such that $a_{n+j} \geqslant a_{n-1}+j+1$, and $a_{n+i} \geqslant a_{n-1}+i$ for all $1 \leqslant i<j$.

Proof. Recall that $b_{n-1}=1$. Set
$$m=\inf \left\{i>0: b_{n+i-1}>1\right\}$$
(possibly $m=+\infty$ ). We claim that $j=\min \{m, 3\}$ works. Again, we distinguish several cases, according to the value of $m$; in each of them we use Lemma 1 without reference.

Case 1: $m=1$, so $b_{n}>1$.
Then $a_{n+1} \geqslant 2 a_{n}+a_{n-1} \geqslant a_{n-1}+2$, as required.

Case 2: $m=2$, so $b_{n}=1$ and $b_{n+1}>1$.
Then we successively get
$$\begin{gathered} a_{n+1}=a_{n}+a_{n-1} \geqslant a_{n-1}+1, \\ a_{n+2} \geqslant 2 a_{n+1}+a_{n}=2\left(a_{n-1}+1\right)+a_{n}=a_{n-1}+\left(a_{n-1}+a_{n}+2\right) \geqslant a_{n-1}+4, \end{gathered}$$
which is even better than we need.

Case 3: $m>2$, so $b_{n}=b_{n+1}=1$.
Then we successively get
$$\begin{gathered} a_{n+1}=a_{n}+a_{n-1} \geqslant a_{n-1}+1, \quad a_{n+2}=a_{n+1}+a_{n} \geqslant a_{n-1}+1+a_{n} \geqslant a_{n-1}+2, \\ a_{n+3} \geqslant a_{n+2}+a_{n+1} \geqslant\left(a_{n-1}+1\right)+\left(a_{n-1}+2\right) \geqslant a_{n-1}+4, \end{gathered}$$
as required. $\square$

Lemmas 1(b) and 2 provide enough information to prove that $\max \left\{a_{n}, a_{n+1}\right\} \geqslant n$ for all $n$ and, moreover, that $a_{n} \geqslant n$ often enough. Indeed, assume that we have found some $n$ with $a_{n-1} \geqslant n-1$. If $n$ is good, then by Lemma 1(b) we have $a_{n} \geqslant n$ as well. If $n$ is bad, then Lemma 2 yields $\max \left\{a_{n+i}, a_{n+i+1}\right\} \geqslant a_{n-1}+i+1 \geqslant n+i$ for all $0 \leqslant i<j$ and $a_{n+j} \geqslant a_{n-1}+j+1 \geqslant n+j$; so $n+j$ is the next index to start with.