Taiwan IMO Selection Camp

The value of $b_0$ is irrelevant since $a_0 = 0$, so we may assume that $b_0 = 1$.

Lemma. We have $a_n \ge 1$ for all $n \ge 1$.

Proof. Let us suppose otherwise in order to obtain a contradiction. Let
$$n \ge 1 \text{ be the smallest integer with } a_n \le 0. \quad (1)$$
Note that $n \ge 2$. It follows that $a_{n-1} \ge 1$ and $a_{n-2} \ge 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 \le 0$, we have $a_{n-1} \le a_{n-2}$. Thus we have
$$a_{n-2} \ge a_{n-1} \ge a_n.$$
Let
$$r \text{ be the smallest index with } a_r \ge a_{r+1} \ge a_{r+2}. \quad (2)$$
Then $r \le n - 2$ by the above, but also $r \ge 2$: if $b_1 = 1$, then $a_2 = a_1 = 1$ and $a_3 = a_2b_2 + a_1 > a_2$; if $b_1 > 1$, then $a_2 = b_1 > 1 = a_1$.
By the minimal choice Eq. (2) of $r$, it follows that $a_{r-1} < a_r$. And since $2 \le r \le n-2$, by the minimal choice Eq. (1) of $n$ we have
$$a_{r-1}, a_r, a_{r+1} > 0.$$
In order to have $a_{r+1} \ge a_{r+2}$, we must have
$$a_{r+2} = a_{r+1}b_{r+1} - a_r$$
so that $b_r \ge 2$. Putting everything together, we conclude that
$$a_{r+1} = a_r b_r \pm a_{r-1} \ge 2a_r - a_{r-1} = a_r + (a_r - a_{r-1}) > a_r,$$
which contradicts Eq. (2).

To complete the problem, we prove that $\max\{a_n, a_{n+1}\} \ge n$ by induction. The case $n = 0, 1$ are given. Assume it is true for all non-negative integers strictly less than $n$, where $n \ge 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 lemma, is at least 1. Hence
$$a_{n+1} = a_n b_n + a_{n-1} \ge a_n + a_{n-1} \ge (n-1) + 1 = n.$$
Thus $\max\{a_n, a_{n+1}\} \ge n$, as desired.

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

Since we defined $b_0 = 1$ there is an index $r$ with $1 \le r \le n-1$ such that
$$b_{n-1}, b_{n-2}, \dots, b_r \ge 2 \text{ and } b_{r-1} = 1.$$
We have $a_{r+1} = a_r b_r + a_{r-1} \ge 2a_r + a_{r-1}$. Thus
$$a_{r+1} - a_r \ge a_r + a_{r-1}.$$
Now we claim that $a_r + a_{r-1} \ge r$. Indeed, this holds by inspection for $r = 1$; for $r \ge 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} \ge r$, as claimed, and therefore $a_{r+1} - a_r \ge r$ by the last inequality in the previous paragraph.
Since $r \ge 1$ and, by the lemma, $a_r \ge 1$, from $a_{r+1} - a_r \ge r$ we get the following two inequalities:
$$a_{r+1} \ge r+1 \text{ and } a_{r+1} > a_r.$$
Now observe that
$$a_m > a_{m-1} \Rightarrow a_{m+1} > a_m \text{ for } m = r+1, r+2, \dots, n-1,$$
since
$$a_{m+1} = a_m b_m - a_{m-1} \ge 2a_m - a_{m-1} = a_m + (a_m - a_{m-1}) > a_m.$$
Thus
$$a_n > a_{n-1} > \dots > a_{r+1} \ge r+1 \Rightarrow a_n \ge n.$$
So $\max\{a_n, a_{n+1}\} \ge n$, as derived.

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 definition of $(a_n)$ since $a_0 = 0$; so we assume that $b_0 > 1$.

Lemma 1. (a) $a_n \ge 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 \ge 1, a_2 = b_1 a_1 \ge 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, \dots, k$ with $k \ge 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} \ge a_k + a_{k-1} > a_k \ge 1,$$
as required.

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

**Subcase 2.1: $b_k > 1$.**
Then
$$a_{k+1} \ge b_k a_k - a_{k-1} \ge a_k + (a_k - a_{k-1}) > a_k \ge 1.$$
**Subcase 2.2: $b_k = b_{k-1} = 1$.**
Then
$$a_{k+1} = a_k + (a_k - a_{k-1}) > a_k \ge 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} \ge 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} \geq a_{n-1} + j + 1, \text{ and } a_{n+i} \geq a_{n-1} + i \text{ for all } 1 \leq i < j.$$
Proof. Recall that $b_{n-1} = 1$. Set
$$m = \inf\{i > 0 : b_{n+i-1} > 1\}$$
(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} \geq 2a_n + a_{n-1} \geq a_{n-1} + 2$, as required.

Case 2: $m = 2$, so $b_n = 1$ and $b_{n+1} > 1$.
Then we successively get
$$\begin{align*} a_{n+1} &= a_n + a_{n-1} \geq a_{n-1} + 1, \\ a_{n+2} &\geq 2a_{n+1} + a_n \geq 2(a_{n-1} + 1) + a_n \\ &= a_{n-1} + (a_{n-1} + a_n + 2) \geq a_{n-1} + 4, \end{align*}$$
which is even better than we need.

Case 3: $m > 2$, so $b_n = b_{n+1} = 1$.
Then we successively get
$$\begin{align*} a_{n+1} &= a_n + a_{n-1} \geq a_{n-1} + 1, & a_{n+2} &= a_{n+1} + a_n \\ &\geq a_{n-1} + 1 + a_n \geq a_{n-1} + 2, \\ a_{n+3} &\geq a_{n+2} + a_{n+1} \geq (a_{n-1} + 1) + (a_{n-1} + 2) \geq a_{n-1} + 4, \end{align*}$$
as required.

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