7
$\begingroup$

Let $\dfrac{A_{n}}{B_{n}}$ be the $n^{th}$ convergent (approximant) $$ \frac{A_{n}}{B_{n}}=b_{0}+\dfrac{a_{1}}{b_{1}+\dfrac{a_{2}}{b_{2}+\dfrac{a_{3}}{\begin{array}{c} b_{3}+ \\ \\ \end{array} \begin{array}{cc} \ddots & \\ & \end{array} +\dfrac{a_{n-1}}{b_{n-1}+\dfrac{a_{n}}{b_{n}}}}}} $$ of a continued fraction. $A_{n}$, $A_{n-1}$, and $A_{n-2}$ satisfy the recurrence $$ \begin{eqnarray*} \begin{pmatrix} A_{n} \\ B_{n} \end{pmatrix} &=& \begin{pmatrix} A_{n-1} & A_{n-2} \\ B_{n-1} & B_{n-2} \end{pmatrix} \begin{pmatrix} b_{n} \\ a_{n} \end{pmatrix} \quad \text{for }n\geq 1, \\ && \\ \text{and } \begin{pmatrix} A_{-1} & A_{0} \\ B_{-1} & B_{0} \end{pmatrix} &=& \begin{pmatrix} 1 & b_{0} \\ 0 & 1 \end{pmatrix} , \end{eqnarray*} $$ which may be proved by induction.

Question: Is there a non inductive proof?

EDIT: I changed the title. Based on the comment below by anon

The numerators and denominators are defined inductively - and I don't believe you'll find an explicit formula for the n-th convergent of an arbitrary continued fraction (though maybe of particular ones with specific patterns, like $\varphi$) - so I don't see any other way to say prove anything about the convergents except inductively.

I reformulate the question to

Question: Is it right that the fundamental recurrence of an arbitrary continued fraction cannot be proved without using mathematical induction?

$\endgroup$
  • 3
    $\begingroup$ I'm not sure what sort of answer you're looking for; it's a recurrence relation, so induction seems very natural to me. You might be able to work out $A_n$ and $B_n$ explicitly and just do algebra, but I reckon finding formulas for $A_n$ and $B_n$ would require induction. $\endgroup$ – Billy Sep 4 '11 at 10:23
  • 1
    $\begingroup$ @Billy: The proof if exists might make further mathematical conclusions. $\endgroup$ – Américo Tavares Sep 4 '11 at 10:35
  • 2
    $\begingroup$ The numerators and denominators are defined inductively - and I don't believe you'll find an explicit formula for the $n$-th convergent of an arbitrary continued fraction (though maybe of particular ones with specific patterns, like $\phi$) - so I don't see any other way to say prove anything about the convergents except inductively. $\endgroup$ – anon Sep 4 '11 at 18:08
  • $\begingroup$ @anon: That's make sense. $\endgroup$ – Américo Tavares Sep 4 '11 at 19:47
3
$\begingroup$

A continued fraction may be defined

  1. as a composition of linear fractional transformations;
  2. as an expression of the form $$b_0 + \cfrac{a_1}{b_1 + \cfrac{a_2}{b_2 + \cfrac{a_3}{b_3 + \cfrac{a_4}{b_4 + \ddots\, \quad }}}}$$
  3. by the fundamental recurrence itself.

In both cases 1 and 2 the recurrence relation is proved by induction, as far as I have seen, namely in recent books.

For a generic continued fraction I now think there is no other way of deriving the fundamental recurrence either from 1 or 2.

$\endgroup$

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.