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?
 A: 
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*}
