The Problem:
Show that
$$
\underbrace{a\left(x_1+\cfrac{1}{ax_2+\cfrac{1}{x_3+\cfrac{1}{{ax_4+{}}_{\ddots}}}}\right)}_\text{2n quotients}=\underbrace{ax_1+\cfrac{1}{x_2+\cfrac{1}{ax_3+\cfrac{1}{{x_4+{}}_{\ddots}}}}}_\text{2n quotients}
$$
My Questions:
- My proof is induction based and I'd like some indicators on how to begin at the left hand side and end up at the RHS.
- Are there any holes in the proof I've written below? I've checked it thoroughly and it looks sound.
My Proof:
Part 1: Context
For the continued fraction
$$
a_1+\cfrac{1}{a_2+\cfrac{1}{{a_3+{}}_\ddots}}
$$
where $a_1$, $a_2$, $a_3\cdots$ are positive integers, called quotients, the first three convergents are
$$
\begin{aligned}
a_1&=\frac{p_1}{q_1}=\frac{a_1}{1} \\ a_1+\cfrac{1}{a_2}&=\frac{p_2}{q_2}=\frac{a_1a_2+1}{a_2} \\ a_1+\cfrac{1}{a_2+\cfrac{1}{a_3}}&=\frac{p_3}{q_3}=\frac{a_3(a_1a_2+1)+1}{a_3a_2+1}=\frac{a_3p_2+p_1}{a_3q_2+q_1}
\end{aligned}
$$
with each successive convergent being a better approximation of the continued fraction. In general, if we denote the numerator of the $n^{th}$ convergent by $p_n$ and denominator by $q_n$, then it can be proven that
$$
\frac{p_n}{q_n}=\frac{a_np_{n-1}+p_{n-2}}{a_nq_{n-1}+q_{n-2}} \text{ for }n=3,4,5\cdots
$$
It can also be proven that $p_n$ and $q_n$ are mutually prime.
For a terminating continued fraction, say with $n$ quotients, the $n^{th}$ convergent is the continued fraction.
Part 2: The Proof
Let us denote the first continued fraction as
$$
\frac{P_n}{Q_n}=\underbrace{a\left(x_1+\cfrac{1}{ax_2+\cfrac{1}{x_3+\cfrac{1}{{ax_4+{}}_{\ddots}}}}\right)}_\text{2n quotients}=a\cdot\frac{p_n}{q_n}
$$
If we denote the $k^{th}$ quotient by $a_k$, where $k\in\mathbb{N}$, then
$$
\begin{aligned}
a_{2k}&=ax_{2k} \\ a_{2k-1}&=x_{2k-1}
\end{aligned}
$$
Now, an even ordered convergent, say $2m^{th}$, is given by
$$
\frac{P_{2m}}{Q_{2m}}=a\cdot\frac{p_{2m}}{q_{2m}}=a\left(\frac{a_{2m}p_{2m-1}+p_{2m-2}}{a_{2m}q_{2m-1}+q_{2m-2}}\right)=a\left(\frac{ax_{2m}p_{2m-1}+p_{2m-2}}{ax_{2m}q_{2m-1}+q_{2m-2}}\right)
$$
Let us denote the second continued fraction as $$ \frac{p^{'}_n}{q^{'}_n}=\underbrace{ax_1+\cfrac{1}{x_2+\cfrac{1}{ax_3+\cfrac{1}{{x_4+{}}_{\ddots}}}}}_\text{2n quotients} $$ If we denote the $k^{th}$ quotient by $a^{'}_k$, where $k\in\mathbb{N}$, then $$ \begin{aligned} a^{'}_{2k}&=x_{2k} \\ a^{'}_{2k-1}&=ax_{2k-1} \end{aligned} $$ Now, the $2m^{th}$ even ordered convergent is given by $$ \frac{p^{'}_{2m}}{q^{'}_{2m}}=\frac{a^{'}_{2m}p^{'}_{2m-1}+p^{'}_{2m-2}}{a^{'}_{2m}q^{'}_{2m-1}+q^{'}_{2m-2}}=\frac{x_{2m}p^{'}_{2m-1}+p^{'}_{2m-2}}{x_{2m}q^{'}_{2m-1}+q^{'}_{2m-2}} $$
We'll prove using Mathematical Induction that each successive convergent of the first contd. fraction is equal to that of the second. $$ \begin{aligned} \frac{P_1}{Q_1}=a&\frac{p_1}{q_1}=a\cdot x_1 \\ &\frac{p^{'}_1}{q^{'}_1}=a\cdot x_1 \\ \frac{P_2}{Q_2}=a&\frac{p_2}{q_2}=a\left(x_1+\frac{1}{ax_2}\right)=ax_1+\frac{1}{x_2} \\ &\frac{p^{'}_2}{q^{'}_2}=ax_1+\frac{1}{x_2} \\ \end{aligned} $$ So, the supposition holds for the first two convergents. Now, let's suppose this holds for $2m^{th}$ convergent, that is $$ \frac{P_{2m}}{Q_{2m}}=a\cdot\frac{p_{2m}}{q_{2m}}=\frac{p^{'}_{2m}}{q^{'}_{2m}}\tag{1} $$
Since the numerators and denominators are mutually prime, we must have both numerators and denominators equaling the corresponding other. That is $$ \begin{aligned} ap_{2m} &= p^{'}_{2m} \\ \implies a(a_{2m}p_{2m-1}+p_{2m-2}) &= a^{'}_{2m}p^{'}_{2m-1}+p^{'}_{2m-2} \\ \implies a(ax_{2m}p_{2m-1}+p_{2m-2}) &= x_{2m}p^{'}_{2m-1}+p^{'}_{2m-2} \\ \implies x_{2m}(a^2p_{2m-1})+ap_{2m-2} &= x_{2m}p^{'}_{2m-1}+p^{'}_{2m-2} \end{aligned} $$ Equating the co-efficients of $x_{2m}$ above, we get $$ a^2p_{2m-1}=p^{'}_{2m-1} \text{ (for odd elements)} \tag{2} $$ $$ ap_{2m-2}=p^{'}_{2m-2} \text{ (for even elements)} \tag{3} $$ Repeating the same for denominators, we get $$ \begin{aligned} q_{2m} &= q^{'}_{2m} \\ \implies a_{2m}q_{2m-1}+q_{2m-2} &= a^{'}_{2m}q^{'}_{2m-1}+q^{'}_{2m-2} \\ \implies ax_{2m}q_{2m-1}+q_{2m-2} &= x_{2m}q^{'}_{2m-1}+q^{'}_{2m-2} \end{aligned} $$ Equating the co-efficients of $x_{2m}$ above, we get $$ q_{2m-2}=q^{'}_{2m-2} \text{ (for even elements)}\tag{4} $$ $$ aq_{2m-1}=q^{'}_{2m-1} \text{ (for odd elements)}\tag{5} $$ Let us now test the suppostion for the index $2m+1$. We have $$ \begin{aligned} \frac{P_{2m+1}}{Q_{2m+1}} &= a\cdot\frac{p_{2m+1}}{q_{2m+1}} \\ &= a\left(\frac{a_{2m+1}p_{2m}+p_{2m-1}}{a_{2m+1}q_{2m}+q_{2m-1}}\right) \\ &= a\left(\frac{x_{2m+1}p_{2m}+p_{2m-1}}{x_{2m+1}q_{2m}+q_{2m-1}}\right) \\ &= \frac{x_{2m+1}\cdot ap_{2m}+ap_{2m-1}}{x_{2m+1}q_{2m}+q_{2m-1}} \\ &= \frac{x_{2m+1}\color{red}{\left(\frac{ap_{2m}}{q_{2m}}\right)}+a\left(\frac{p_{2m-1}}{q_{2m}}\right)}{x_{2m+1}+\left(\frac{q_{2m-1}}{q_{2m}}\right)} \\ &= \frac{x_{2m+1}\color{red}{\left(\frac{p^{'}_{2m}}{q^{'}_{2m}}\right)}+a\left(\frac{p_{2m-1}}{q_{2m}}\right)}{x_{2m+1}+\left(\frac{q_{2m-1}}{q_{2m}}\right)} \text{ from (1)} \\ &= \frac{x_{2m+1}\cdot p^{'}_{2m}+ap_{2m-1}\color{blue}{\left(\frac{q^{'}_{2m}}{q_{2m}}\right)}}{x_{2m+1}\cdot q^{'}_{2m}+q_{2m-1}\color{blue}{\left(\frac{q^{'}_{2m}}{q_{2m}}\right)}} \\ &= \frac{x_{2m+1}\cdot p^{'}_{2m}+\color{red}{ap_{2m-1}}\color{blue}{(1)}}{x_{2m+1}\cdot q^{'}_{2m}+q_{2m-1}\color{blue}{(1)}} \text{ from (4)} \\ &= \frac{x_{2m+1}\cdot p^{'}_{2m}+\color{red}{\left(\frac{p^{'}_{2m-1}}{a}\right)}}{x_{2m+1}\cdot q^{'}_{2m}+q_{2m-1}} \text{ from (2)} \\ &= \frac{ax_{2m+1}\cdot p^{'}_{2m}+p^{'}_{2m-1}}{ax_{2m+1}\cdot q^{'}_{2m}+\color{blue}{aq_{2m-1}}} \\ &= \frac{ax_{2m+1}\cdot p^{'}_{2m}+p^{'}_{2m-1}}{ax_{2m+1}\cdot q^{'}_{2m}+\color{blue}{q^{'}_{2m-1}}} \text{ from (5)}\\ &= \frac{a^{'}_{2m+1}\cdot p^{'}_{2m}+p^{'}_{2m-1}}{a^{'}_{2m+1}\cdot q^{'}_{2m}+q^{'}_{2m-1}} \\ &= \frac{p^{'}_{2m+1}}{q^{'}_{2m+1}} \end{aligned} $$ Therefore, the supposition is true for all $n$ by Mathematical Induction and consequently we've proven that each convergent of the first contd. fraction is equal to the corresponding convergent on the second and therefore both fractions represent the same value.