Proof of the formula for the convergents of continued fractions: How to start?

Question

I'm reading Vinogradov's "Elements of Number Theory", am having trouble proving one of his early propositions, and ask for a little help getting started.

In Chapter 1, he introduces the idea of convergents of a continued fraction, e.g. $\delta_s$, where $\delta_s$ is defined by

$\delta_1 = q_1$
$\delta_2 = q_1 + \frac{1}{q_2}$
$\delta_3 = q_1 + \frac{1}{q_2 + \frac{1}{q_3}}$
etc., where $q_s$ has its usual meaning in the context of continued fractions.

He also gives a nice-looking formula for $\delta_s$:

$\delta_s = \frac{P_s}{Q_s}$,

where $P_s$ is defined recursively by

$P_0 = 1$, $P_1 = q_1$, and $P_s = q_sP_{s-1} + P_{s-2}$ for $s\geq2$,

and $Q_s$ is defined similarly, by

$Q_0 = 0$, $Q_1 = 1$, and $Q_s = q_sQ_{s-1} + Q_{s-2}$ for $s\geq2$.

He shows that this nice-looking formula is true for $s\leq3$, but not beyond. My attempts to prove it for arbitrary $s$, using induction, have thus far led to a mess of notation and little else.

How would you get started?

Answer 1

He shows that this nice-looking formula is true for $s\leq3$, but not beyond. My attempts to prove it for arbitrary $s$, using induction, have thus far led to a mess of notation and little else.

Concerning the notation the generic $\delta_s $ is the continued fraction

$$\delta_s=q_1+\cfrac{1}{q_2+\cfrac{1}{\begin{array}{ccc}q_{3}+ & & \\& \ddots & \\& & +\cfrac{1}{q_{s-1}+\cfrac{1}{q_{s}}}\end{array}}} .$$

How would you get started?

In the inductive step we need to prove that for arbitrary integer $k\geq 3$ if $P_{k}=q_{k}P_{k-1}+P_{k-2}$, $Q_{k}=q_{k+1}Q_{k}+Q_{k-1}$, and \begin{equation*} \delta _{k}=\frac{q_{k}P_{k-1}+P_{k-2}}{q_{k}Q_{k-1}+Q_{k-2}}=\frac{P_{k}}{Q_{k}}, \end{equation*} then \begin{equation*} \delta _{k+1}=\frac{q_{k+1}P_{k}+P_{k-1}}{q_{k+1}Q_{k}+Q_{k-1}}=\frac{P_{k+1} }{Q_{k+1}}. \end{equation*}

Sketch of the proof. Notice that we obtain $\delta _{k+1}$ from $\delta _{k}$ by replacing $q_{k}$ with $q_{k}+1/q_{k+1} $. (see 3.d in the book.) The rest follows algebraically.

---

Added (in response to OP's comment). Firstly we obtain

\begin{equation*} \delta _{k+1}=\frac{P_{k}+P_{k-1}/q_{k+1}}{Q_{k}+Q_{k-1}/q_{k+1}}. \end{equation*}

Then, since the numerator $P_{k}+P_{k-1}/q_{k+1}$ and denominator $Q_{k}+Q_{k-1}/q_{k+1}$ are not yet integers of the form \begin{eqnarray*} P_{k+1} &=&q_{k+1}P_{k}+P_{k-1} \\ Q_{k+1} &=&q_{k+1}Q_{k}+Q_{k-1}, \end{eqnarray*} to complete the proof we multiply both by $q_{k+1}$, allowing us to write $\delta _{k+1}$ in the final form \begin{equation*} \delta _{k+1}=\frac{q_{k+1}P_{k}+P_{k-1}}{q_{k+1}Q_{k}+Q_{k-1}}=\frac{P_{k+1} }{Q_{k+1}},\qquad \text{with }P_{k+1}\text{, }Q_{k+1}\text{ integers.} \end{equation*}