This is not a very hard problem; you just keep adding inductive conditions until you don't need anymore! Solution was found with Carl Schildkraut at MOP. First we show that the sequence is strictly positive except $a_0$, and that the sequence can't decrease twice in a row; the proof is the same for both claims. Lemma: $a_i > 0$ for all $i > 0.$ Also, if $a_i > a_{i+1}$ then $a_{i+1} < a_{i+2}.$ Proof: We can check this by hand for $i = 1, 2, 3$ say. If $a_{n+1} \le 0$ then we certainly need $a_n \le a_{n-1}$ and $b_{n-1} > 1.$ If $a_n = b_{n-1} a_{n-1} + a_{n-2}$ then clearly $a_n > a_{n-1}$ by induction. So $a_{n-1} \ge a_n = b_{n-1} a_{n-1} - a_{n-2} \ge 2 a_{n-1} - a_{n-2}$, and $b_{n-2} > 1.$ Therefore, $a_{n-2} \ge a_{n-1}$ too. We can just keep propagating this to the beginning of the sequence, an obvious contradiction. The second claim follows similarly. Say $a_n > a_{n+1}$. If $a_{n+2} = b_{n+1} a_{n+1} + a_n$ then the claim is clear. So $a_{n+2} = b_{n+1} a_{n+1} - a_n$, so $b_n > 1.$ Now say $a_n > a_{n+1}$ and $b_n > 1.$ Now, $a_{n+1} = b_na_n - a_{n-1}$. As $b_n > 1$, we need $a_n < a_{n-1}$ and $b_{n-1} > 1.$ Propagating back gives a contradiction. $\blacksquare$ We now use induction on the following claim. Claim: For each positive integer $n \ge 1$, one of the following 4 conditions holds. 1. $a_n \ge n$. 2. $a_{n+1} \ge n+1.$ 3. $(a_{n-1}, a_n, a_{n+1}) = (1, n-1, n).$ 4. $(a_{n-1}, a_n, a_{n+1}) = (n-1, 1, n).$ We can verify this by hand for say $n \le 3$. Assume $n > 3$ from now on. Proof: Assume 2 holds for $n = k$. Then obviously 1 holds for $n = k+1.$ Assume 1 holds but not 2. Then $a_{n+1} \le a_n$, so from the Lemma we know that $a_{n-1} \le a_n$. If $b_{n-1} = 1$ then $a_{n+1} = b_n a_n + a_{n-1} > a_n$, contradiction. So $b_{n-1} > 1$, and $a_{n+1} = b_n a_n - a_{n-1}.$ As $a_n > a_{n-1}$ we need $b_n = 1.$ Now $a_{n+2} = b_{n+1} a_{n+1} + a_n.$ Then $a_{n+2} \ge n+2$ (situation 2) unless $b_{n+1} = 1$ and $a_{n+1} = 1$, which is situation 4. Now, say situation 3 holds. It is easy to check that $b_n(n-1) - 1 \neq n$ if $n > 3$, and $b_n(n-1) + 1 = n$ only if $b_n = 1.$ So then $a_{n+2} \ge 2n-1 \ge n+2$ as desired (situation 2). Now, say situation 4 holds. As $a_{n-1} > a_n$ from Lemma essentially we get that $b_{n-1} = b_n = 1$, so $a_{n+2} = b_{n+1} n + 1.$ If $b_{n+1} = 1$, we get to situation 3. Otherwise, $a_{n+2} \ge 2n + 1 \ge n+2$, so we get to situation 2. This completes the induction so we're done. Obviously $\max(a_n, a_{n+1}) \ge n$ in all 4 cases.

Lemma 1. For $i\geq1$, $a_i>0$ and if $b_{i-1}>1$, $a_i>a_{i-1}$. Proof. It is trivial for $i=1$, and assume that the statement holds for $1\leq i\leq n$. (1) $b_n=b_{n-1}=1:$ $a_{n+1}=a_n+a_{n-1}>0$ (2) $b_n=1, b_{n-1}>1:$ $a_{n+1}=a_n-a_{n-1}>0$ (3) $b_n>1, b_{n-1}=1:$ $a_{n+1}=a_nb_n+a_{n-1}>a_n>0$ (4) $b_n, b_{n-1}>1:$ $a_{n+1}=a_nb_n-a_{n-1}=a_n(b_n-1)+(a_n-a_{n-1})>a_n>0$ So it holds for $i=n+1$. $\blacksquare$ Lemma 2. For $i\geq 2$, if $b_{i-2}=b_{i-1}=1$, $a_i\geq i-1$, and if $b_{i-1}>1$, $a_i\geq i$. Proof. It is trivial for $i=2$, and assume that the statement holds for $2\leq i\leq n$. (1) $b_{n-1}=b_n=1, b_{n-2}=1:$ $a_{n+1}=a_n+a_{n-1}\geq (n-1)+1=n$ (2) $b_{n-1}=b_n=1, b_{n-2}>1:$ $a_{n+1}=a_n+a_{n-1}\geq 1+(n-1)=n$ (3) $b_n>1, b_{n-1}=1, b_{n-2}=1:$ $a_{n+1}=a_nb_n+a_{n-1}\geq 2(n-1)+1=2n-1\geq n+1$ (4) $b_n>1, b_{n-1}=1, b_{n-2}>1:$ $a_{n+1}=a_nb_n+a_{n-1}\geq 1\cdot2+(n-1)=n+1$ (5) $b_n>1, b_{n-1}>1:$ $a_{n+1}=a_nb_n-a_{n-1}=a_n(b_n-1)+(a_n-a_{n-1})\geq n\cdot1+1=n+1$ So it holds for $i=n+1$. $\blacksquare$ By Lemma 2, (1) $b_{2016}>1:$ $a_{2017}\geq2017$ (2) $b_{2016}=1,b_{2017}>1:$ $a_{2018}\geq2018>2017$ (3) $b_{2016}=b_{2017}=1:$ $a_{2018}\geq2017$ $\therefore max\{a_{2017}, a_{2018}\}\geq 2017$ $\blacksquare$

Nice problem, also surprised cuz this is the first problem of Taiwan's 18 third Mock. Obviously, $2017$ can be replace by any natural number $n$. Claim . $(a_n)_{n=1}^\infty$ is a positive integer sequence. Proof. If not, let $n$ be the first natural number such that $a_n\le 0$, we use backward-induction to prove that $$a_k \ge a_{k+1} \qquad \text{and} \qquad b_k>1 \forall k=1, 2, \ldots n-2$$Since $a_{n-2}, a_{n-1}$ are positive, hence the only possibility is that $b_{n-2}>1$, and $$0\ge a_n=a_{n-1}b_{n-1}-a_{n-2} \ge a_{n-1} - a_{n-2} $$, hence $a_{n-2} \ge a_{n-1}$. If $a_{k}\ge a_{k+1}$ is true (where $1\le k \le n-2$) Since$b_k >1$ , the only possibility is that $b_{k-1}>1$ and $$a_{k+1} = b_ka_{k}-a_{k-1} \ge 2a_k-a_{k-1}$$, hence $a_{k-1} \ge 2a_{k}-a_{k+1} \ge a_k$. So by induction, the statement is true. However, $a_0 < a_1$we get the contradiction. So the assumption is wrong, the claim is true. $\square$ Main Problem Now we use induction to prove that $$ max\{a_n, a_{n+1}\} \ge n \qquad \forall n\ge 0$$$n=0,1$ is obviously true. If the statement holds for $1, 2, ... ,n$, we show that $n+1$ is true. case 1. $b_{n-1}=1$ If $b_n>1$, then $a_{n+1} = a_nb_n+a_{n-1} \ge 2a_n + a_{n-1} \ge 1+n$, else $b_n=1$, then $a_{n+2}=b_{n+1}a_{n+1}+a_n \ge n+1$. case 2. $b_{n-1} >1$ Let $k$ be the largest integer such that $b_k = 1$ , $k< n-1$ (We may say $b_0=1$ that doesn't matter), it is easy to prove $a_{k+1}<a_{k+2}<\ldots<a_n$ using induction. By inductive hypothesis, $a_{k+2}\ge 2a_{k+1}+a_{k}\ge k+2$, hence $a_n\ge n$. If $b_n=1$, then $a_{n+2} \ge a_{n+1}+a_n \ge n+1$, else $b_n>1$, then $a_{n+1} \ge 2a_n-a_{n-1} \ge n+1$. So the statement holds for $n+1$, by induction we're done. $\blacksquare$

Nice but not too hard. Claim: If $b_i > 1$, then $a_{i+1} > a_i$ Proof: Suppose not, and let $j$ be the minimal such counterexample. Clearly, $j > 0$. Note that we have $a_j \ge a_{j+1} = a_jb_j \pm a_{j-1} \ge 2a_j \pm a_{j-1}$, so if $b_{j-1} = 1$, then clearly the RHS is too big so $b_{j-1} > 1$ which gives $a_{j-1} \ge a_j$ contradicting minimality. $\square$ Suppose we had $a_n \le 0$ for some minimal $n$, then we must have $b_{n-2} > 1$ and $a_{n-1} \ge a_{n-2}$, a contradiction to the claim. So $a_i$ consists of only positive integers (apart from $a_0 = 0$). Now, by induction, I will prove that one of $a_n, a_{n+1}$ is $\ge n$, which finishes by picking $n = 2017$. The base case is simple so suppose it is true until $n$ and we must prove it for $n+1$, assume it failed and so $a_{n+1}, a_{n+2} \le n$. Since $n \ge a_{n+2} = b_{n+1}a_{n+1} \pm a_n$, if $b_n = 1$, then since at least one of $a_n, a_{n+1}$ is $\ge n$ and the other is at least $1$, the RHS is at least $n+1$ contradiction. So $b_n > 1$. So we have $n \ge a_{n+1} \ge 2a_n \pm a_{n-1}$, using similar logic as earlier, we must have $b_{n-1} > 1$ too, so $a_{n-1} + n \ge 2a_n \ge 2(2a_{n-1} \pm a_{n-2})$. Continuing similarly, we can inductively get that $b_k > 1$ for all $1 \le k \le n$. But by the claim, this implies that the sequence is strictly increasing (until the $n$th term), which is again a contradiction to the fact that $a_{n+2} \le n$. So the induction holds and so indeed one of $a_n, a_{n+1} \ge n$ always, as desired. $\blacksquare$