Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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. –  Billy Sep 4 '11 at 10:23
1  
@Billy: The proof if exists might make further mathematical conclusions. –  Américo Tavares Sep 4 '11 at 10:35
2  
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. –  anon Sep 4 '11 at 18:08
    
@anon: That's make sense. –  Américo Tavares Sep 4 '11 at 19:47
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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