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⩾1$ for all $n⩾1$.

Proof. Let us suppose otherwise in order to obtain a contradiction. Let $$\begin{array}{c}n⩾1\text{ be the smallest integer with }{a}_n⩽0\text{. }\end{array}\text{\hspace{1em}(1)}$$ Note that $n⩾2$. It follows that $a_{n-1}⩾1$ and $a_{n-2}⩾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⩽0$, we have $a_{n-1}⩽a_{n-2}$. Thus we have $a_{n-2}⩾a_{n-1}⩾a_n$.

Let $$\begin{array}{c}r\text{ be the smallest index with }{a}_r⩾a_{r+1}⩾a_{r+2}\text{. }\end{array}\text{\hspace{1em}(2)}$$ Then $r⩽n-2$ by the above, but also $r⩾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⩽r⩽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}⩾a_{r+2}$, we must have $a_{r+2}=a_{r+1}{b}_{r+1}-a_r$ so that $b_r⩾2$. Putting everything together, we conclude that $$a_{r+1}=a_r{b}_r\pm a_{r-1}⩾2a_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\}⩾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⩾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}⩾a_n+a_{n-1}⩾(n-1)+1=n.$$ Thus $\max \left\{a_n,a_{n+1}\right\}⩾n$, as desired.

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

Since we defined $b_0=1$ there is an index $r$ with $1⩽r⩽n-1$ such that $$b_{n-1},b_{n-2},\dots ,b_r⩾2\text{ and }{b}_{r-1}=1.$$ We have $a_{r+1}=a_r{b}_r+a_{r-1}⩾2a_r+a_{r-1}$. Thus $a_{r+1}-a_r⩾a_r+a_{r-1}$.

Now we claim that $a_r+a_{r-1}⩾r$. Indeed, this holds by inspection for $r=1$; for $r⩾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}⩾r$, as claimed, and therefore $a_{r+1}-a_r⩾r$ by the last inequality in the previous paragraph.

Since $r⩾1$ and, by the lemma, $a_r⩾1$, from $a_{r+1}-a_r⩾r$ we get the following two inequalities: $$a_{r+1}⩾r+1\text{ and }{a}_{r+1}>a_r.$$ Now observe that $$a_m>a_{m-1}⟹a_{m+1}>a_m\text{ for }m=r+1,r+2,\dots ,n-1\text{, }$$ since $a_{m+1}=a_m{b}_m-a_{m-1}⩾2a_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}⩾r+1⟹a_n⩾n$$ So $\max \left\{a_n,a_{n+1}\right\}⩾n$, as desired.

---

Alternative solution.

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⩾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⩾1,a_2=b_1{a}_1⩾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⩾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}⩾a_k+a_{k-1}>a_k⩾1$, as required.

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

Subcase 2.1: $b_k>1$. Then $a_{k+1}⩾b_k{a}_k-a_{k-1}⩾a_k+\left(a_k-a_{k-1}\right)>a_k⩾1$.

Subcase 2.2: $b_k=b_{k-1}=1$. Then $a_{k+1}=a_k+a_{k-1}>a_k⩾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}⩾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}⩾a_{n-1}+j+1$, and $a_{n+i}⩾a_{n-1}+i$ for all $1⩽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}⩾2a_n+a_{n-1}⩾a_{n-1}+2$, as required.

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

Case 3: $m>2$, so $b_n=b_{n+1}=1$. Then we successively get $$\begin{array}{c}{a}_{n+1}=a_n+a_{n-1}⩾a_{n-1}+1,a_{n+2}=a_{n+1}+a_n⩾a_{n-1}+1+a_n⩾a_{n-1}+2,\\ a_{n+3}⩾a_{n+2}+a_{n+1}⩾\left(a_{n-1}+1\right)+\left(a_{n-1}+2\right)⩾a_{n-1}+4,\end{array}$$ as required. $\square$

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