[proofplan] We prove the formula by isolating the effect of appending a final entry to a fixed prefix. The key auxiliary identity says that replacing the last input by an arbitrary positive rational number $t$ gives a linear fractional expression in $t$ whose coefficients are the two adjacent continuants of the prefix. Applying this identity with $t = a_k$ gives the desired formula for the $k$th convergent, and the positivity of the denominators follows from the same recurrence because all partial quotients after $a_0$ are positive. [/proofplan]

[step:Compute the initial continuants and prove positivity of the denominators] From the recurrence at $k = 0$ we have \begin{align*} p_0 = a_0p_{-1}+p_{-2}=a_0,\qquad q_0 = a_0q_{-1}+q_{-2}=1. \end{align*} Thus $q_0 > 0$. For $k \geq 1$, we prove $q_k > 0$ by induction on $k$. The case $k=1$ gives \begin{align*} q_1 = a_1q_0+q_{-1}=a_1>0, \end{align*} because $a_1 \in \mathbb{N}$. If $k \geq 2$ and $q_{k-1}>0$, $q_{k-2}>0$, then \begin{align*} q_k = a_kq_{k-1}+q_{k-2}>0, \end{align*} because $a_k \in \mathbb{N}$. Hence $q_k>0$ for every $0 \leq k \leq n$. [/step]

[step:Prove the linear fractional formula for a variable final entry]This auxiliary step is needed only when $n \geq 1$. In that case, fix an integer $r$ with $0 \leq r \leq n-1$. Define $C_r$ to be the map from $\mathbb{Q}_{>0}$ to $\mathbb{Q}$ given by \begin{align*} C_r(t) := [a_0;a_1,\dots,a_r,t]. \end{align*} We claim that \begin{align*} C_r(t)=\frac{t p_r+p_{r-1}}{t q_r+q_{r-1}}. \end{align*} We prove this by induction on $r$. For $r=0$, \begin{align*} C_0(t) = [a_0;t] = a_0+\frac{1}{t} = \frac{t a_0+1}{t} = \frac{t p_0+p_{-1}}{t q_0+q_{-1}}. \end{align*} Assume the formula holds for $r-1$, where $1 \leq r \leq n-1$. Define \begin{align*} s := a_r+\frac{1}{t}. \end{align*} Since $a_r \in \mathbb{N}$ and $t \in \mathbb{Q}_{>0}$, we have $s \in \mathbb{Q}_{>0}$. By the recursive definition of finite [continued fractions](/page/Continued%20Fractions), \begin{align*} C_r(t) = [a_0;a_1,\dots,a_{r-1},s]. \end{align*} Applying the induction hypothesis to the positive rational number $s$ gives \begin{align*} C_r(t)= \frac{s p_{r-1}+p_{r-2}}{s q_{r-1}+q_{r-2}}. \end{align*} The denominator is nonzero. The first step gives $q_{r-1}>0$; also $q_{r-2}\geq 0$, because $q_{-1}=0$ when $r=1$ and $q_j>0$ for every $j\geq 0$. Since $s>0$, we have $s q_{r-1}+q_{r-2}>0$. Substituting \begin{align*} s=a_r+\frac{1}{t} \end{align*} gives \begin{align*} C_r(t)= \frac{\left(a_r+\frac{1}{t}\right)p_{r-1}+p_{r-2}} {\left(a_r+\frac{1}{t}\right)q_{r-1}+q_{r-2}}. \end{align*} Multiplying numerator and denominator by $t>0$ yields \begin{align*} C_r(t)= \frac{t(a_rp_{r-1}+p_{r-2})+p_{r-1}} {t(a_rq_{r-1}+q_{r-2})+q_{r-1}}. \end{align*} Using the defining recurrence for $p_r$ and $q_r$, this becomes \begin{align*} C_r(t)= \frac{t p_r+p_{r-1}}{t q_r+q_{r-1}}. \end{align*}[/step]

[guided]The purpose of introducing $C_r(t)$ is to separate the fixed prefix $a_0,\dots,a_r$ from the final input $t$. Once this dependence is written as a linear fractional function of $t$, the usual recurrence appears by substituting the next partial quotient. When $n \geq 1$, fix $r$ with $0 \leq r \leq n-1$. Define $C_r$ to be the map from $\mathbb{Q}_{>0}$ to $\mathbb{Q}$ given by \begin{align*} C_r(t) := [a_0;a_1,\dots,a_r,t]. \end{align*} We prove \begin{align*} C_r(t)=\frac{t p_r+p_{r-1}}{t q_r+q_{r-1}} \end{align*} by induction on $r$. For $r=0$, the continued fraction has only the prefix entry $a_0$ and the variable final entry $t$. Therefore \begin{align*} C_0(t) = [a_0;t] = a_0+\frac{1}{t} = \frac{t a_0+1}{t}. \end{align*} The recurrence already gave $p_0=a_0$, $p_{-1}=1$, $q_0=1$, and $q_{-1}=0$, so this is exactly \begin{align*} C_0(t)=\frac{t p_0+p_{-1}}{t q_0+q_{-1}}. \end{align*} Now assume the formula is known for $r-1$, where $1 \leq r \leq n-1$. The final two entries of \begin{align*} [a_0;a_1,\dots,a_r,t] \end{align*} combine into one positive rational number. Define \begin{align*} s := a_r+\frac{1}{t}. \end{align*} Because $a_r \in \mathbb{N}$ and $t>0$, the number $s$ is positive, so it is a valid input for the induction hypothesis. By the recursive definition of finite continued fractions, \begin{align*} C_r(t)=[a_0;a_1,\dots,a_{r-1},s]. \end{align*} The induction hypothesis gives \begin{align*} C_r(t) = \frac{s p_{r-1}+p_{r-2}}{s q_{r-1}+q_{r-2}}. \end{align*} This quotient is defined because $s>0$ and $q_{r-1}>0$ by the first step. We also have $q_{r-2}\geq 0$: if $r=1$, then $q_{r-2}=q_{-1}=0$, while if $r\geq 2$, then $q_{r-2}>0$ by the positivity already proved. Hence \begin{align*} s q_{r-1}+q_{r-2}>0. \end{align*} Substituting \begin{align*} s=a_r+\frac{1}{t} \end{align*} gives \begin{align*} C_r(t) = \frac{\left(a_r+\frac{1}{t}\right)p_{r-1}+p_{r-2}} {\left(a_r+\frac{1}{t}\right)q_{r-1}+q_{r-2}}. \end{align*} Since $t>0$, multiplying both numerator and denominator by $t$ does not change the quotient. Hence \begin{align*} C_r(t)= \frac{t(a_rp_{r-1}+p_{r-2})+p_{r-1}} {t(a_rq_{r-1}+q_{r-2})+q_{r-1}}. \end{align*} The expressions in parentheses are exactly the recurrence definitions \begin{align*} p_r=a_rp_{r-1}+p_{r-2},\qquad q_r=a_rq_{r-1}+q_{r-2}. \end{align*} Therefore \begin{align*} C_r(t)=\frac{t p_r+p_{r-1}}{t q_r+q_{r-1}}, \end{align*} which completes the induction.[/guided]

[step:Evaluate the formula at the actual final partial quotient] For $k=0$, the initial computation gives \begin{align*} [a_0]=a_0=\frac{p_0}{q_0}. \end{align*} Let $k$ be an integer with $1 \leq k \leq n$. Apply the variable-final-entry formula with $r=k-1$ and $t=a_k$. Since $a_k \in \mathbb{N}$, this substitution is allowed. We obtain \begin{align*} [a_0;a_1,\dots,a_k] = \frac{a_k p_{k-1}+p_{k-2}}{a_k q_{k-1}+q_{k-2}}. \end{align*} The denominator is $q_k$, which is positive by the first step. Again by the defining recurrence for $p_k$ and $q_k$, \begin{align*} [a_0;a_1,\dots,a_k] = \frac{p_k}{q_k}. \end{align*} Together with the positivity of $q_k$ proved above, this establishes the asserted formula for every $0 \leq k \leq n$. [/step]