Problem 1447

If the given pair of inequalities do not hold, then the sequence $(a_n)$ quickly degenerates into a sequence consisting of only 0s and 1s. There are basically two such cases to analyse, namely $a_1 = 0$ and $a_1 = 1$, since the two other cases $a_1 = a_2$ and $a_1 = a_2 - 1$ are seen to be equivalent to those two cases by means of the basic identity
$$\binom{N}{M} = \binom{N}{N-M}.$$
Each of the cases $a_1 = 0$ and $a_1 = 1$ can be broken into three subcases, depending on whether $a_2$ equals 0, 1, or a larger number. In all six cases, if we eliminate a few terms from the beginning of the sequence $(a_n)$, we are left with either the constant sequence $1, 1, 1, \dots$, or the alternating sequence $0, 1, 0, 1, 0, 1, \dots$. We leave it to the reader to check that this is true in each of the six subcases.

On the other hand, if the inequalities both hold then we can show by induction that $a_{n+1} \ge 3a_n/2$ for all $n > 2$. This follows readily by using the following lemma for the inductive step.

Lemma. Let $A, B$, and $C$ be positive integers such that $2 \le A \le B - 2$ and
$$C = \binom{B}{A}.$$
Then $2 \le B \le C - 2$ and $C \ge 3B/2$.

Proof. Recall the well-known fact that for a fixed positive integer $B$, the binomial coefficients $\binom{B}{A}$ increase as the integer $A \in [0, B]$ is moved towards $B/2$. Thus in the above lemma, $C$ is minimal when $A = 2$ or $A = B - 2$. In both of these cases, $\binom{B}{A}$ equals $B(B-1)/2$ and, since $B \ge 4$, we readily get the desired lower bounds $3B/2$ and $B + 2$ for $C$.