# Is it right that the fundamental recurrence of an arbitrary continued fraction cannot be proved without induction?

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?

• 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
• @Billy: The proof if exists might make further mathematical conclusions. – Américo Tavares Sep 4 '11 at 10:35
• 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

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.