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

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?

• 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? I'm not quite sure what you are doing. What are you trying to prove? – Simply Beautiful Art Mar 6 '17 at 21:18
• @SimplyBeautifulArt : I'm trying to prove that $\delta_s = \frac{P_s}{Q_s}$, regardless of s. $\delta_s$ is defined as a messy continued fraction. – John Fogg Mar 6 '17 at 21:20
• You are going to need to start with one explicit recursive formula for $\delta_s$ in order to prove another explicit recursive formula for $\delta_s$. What explicit recursive formula are you starting with? – Lee Mosher Mar 6 '17 at 21:27
• No, but, with a tiny tweak it is easily converted into a true recursive formula: define $[q_1,...,q_n]$ by induction on $n$ as $q_1 + 1 / [q_2,...,q_n]$, starting with $[q_1]=q_1$. – Lee Mosher Mar 6 '17 at 22:37
• Alternatively, find another book. Most intro Number Theory texts will have a chapter on continued fractions, and will do this explicitly instead of leaving it as an exercise. – Gerry Myerson Mar 7 '17 at 5:59

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

• This reasoning requires a small cognitive jump, right? We have to think of $\delta_{k+1}$ not as a continued fraction of order $k+1$ whose last term is $q_{k+1}$, but as a continued fraction of order $k$ whose last term is $q_k + \frac{1}{q_{k+1}}$. Therefore we must think of the $q_i$ as possibly being rationals, not just integers. – John Fogg Mar 10 '17 at 0:46