[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*}
[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]
[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]
