[proofplan] The recurrence for continued fraction denominators expresses $q_{n+1}$ as $a_{n+1}q_n + q_{n-1}$. Since every partial quotient $a_{n+1}$ with positive index is at least $1$, the desired Fibonacci-type inequality follows once the preceding denominators are known to be positive. We first prove positivity by induction, then use the recurrence to obtain the lower growth inequality. Finally, the inequality implies that both the even and odd subsequences increase at least linearly, so the whole sequence diverges to infinity. [/proofplan] [step:Prove positivity of all convergent denominators] We prove by induction that $q_n \geq 1$ for every integer $n \geq 0$. The initial value is $q_0 = 1$. Also, \begin{align*} q_1 = a_1q_0 + q_{-1} = a_1 \cdot 1 + 0 = a_1 \geq 1, \end{align*} because $a_1 \in \mathbb{N}$. Assume now that $n \geq 1$ and that $q_{n-1} \geq 1$ and $q_n \geq 1$. Since $a_{n+1} \in \mathbb{N}$, we have $a_{n+1} \geq 1$. The recurrence gives \begin{align*} q_{n+1} = a_{n+1}q_n + q_{n-1} \geq 1 \cdot q_n + q_{n-1} \geq 1 + 1 \geq 1. \end{align*} Thus, by induction, $q_n \geq 1$ for every $n \geq 0$. [/step] [step:Use the recurrence to get the Fibonacci-type lower bound] Let $n \geq 1$. By the defining recurrence, \begin{align*} q_{n+1} = a_{n+1}q_n + q_{n-1}. \end{align*} Since $a_{n+1} \in \mathbb{N}$, we have $a_{n+1} \geq 1$. Since the previous step gives $q_n \geq 1$, multiplication preserves the inequality: \begin{align*} a_{n+1}q_n \geq q_n. \end{align*} Substituting this into the recurrence yields \begin{align*} q_{n+1} = a_{n+1}q_n + q_{n-1} \geq q_n + q_{n-1}. \end{align*} This proves the claimed inequality for every $n \geq 1$. [guided] Fix an integer $n \geq 1$. The recurrence is the only structural fact about the denominator sequence that we need: \begin{align*} q_{n+1} = a_{n+1}q_n + q_{n-1}. \end{align*} The point of the hypothesis that the continued fraction is simple is that every partial quotient after $a_0$ is a positive integer. Therefore $a_{n+1} \in \mathbb{N}$, so $a_{n+1} \geq 1$. We also already proved that $q_n \geq 1$, hence in particular $q_n$ is nonnegative. Multiplying the inequality $a_{n+1} \geq 1$ by $q_n$ preserves the direction of the inequality: \begin{align*} a_{n+1}q_n \geq q_n. \end{align*} Replacing the term $a_{n+1}q_n$ in the recurrence by this lower bound gives \begin{align*} q_{n+1} = a_{n+1}q_n + q_{n-1} \geq q_n + q_{n-1}. \end{align*} Thus the denominators grow at least as fast as a Fibonacci-type recurrence, because each new denominator is bounded below by the sum of the two preceding denominators. [/guided] [/step] [step:Deduce divergence from the lower bound] We show that both parity subsequences tend to infinity. For every $k \geq 0$, applying the inequality with $n = 2k+1$ gives \begin{align*} q_{2k+2} \geq q_{2k+1} + q_{2k}. \end{align*} Since $q_{2k+1} \geq 1$, this implies \begin{align*} q_{2k+2} \geq q_{2k} + 1. \end{align*} Starting from $q_0 = 1$, induction on $k$ gives \begin{align*} q_{2k} \geq k+1 \quad \text{for every } k \geq 0. \end{align*} Similarly, for every $k \geq 0$, applying the inequality with $n = 2k+2$ gives \begin{align*} q_{2k+3} \geq q_{2k+2} + q_{2k+1}. \end{align*} Since $q_{2k+2} \geq 1$, this implies \begin{align*} q_{2k+3} \geq q_{2k+1} + 1. \end{align*} Starting from $q_1 = a_1 \geq 1$, induction on $k$ gives \begin{align*} q_{2k+1} \geq k+1 \quad \text{for every } k \geq 0. \end{align*} Let $M > 0$. Choose an integer $K \geq M$. If $n \geq 2K$, then either $n = 2k$ with $k \geq K$ or $n = 2k+1$ with $k \geq K$. In both cases the corresponding parity estimate gives \begin{align*} q_n \geq k+1 \geq K+1 > M. \end{align*} Therefore $q_n \to \infty$ as $n \to \infty$. [/step]