1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Simply Beautiful Art Mar 6 '17 at 21:18
  • $\begingroup$ @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. $\endgroup$ – John Fogg Mar 6 '17 at 21:20
  • 1
    $\begingroup$ 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? $\endgroup$ – Lee Mosher Mar 6 '17 at 21:27
  • 2
    $\begingroup$ 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$. $\endgroup$ – Lee Mosher Mar 6 '17 at 22:37
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Mar 7 '17 at 5:59
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – John Fogg Mar 10 '17 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.