Continued fractions using recursion relations

continued-fractionselementary-number-theorynumber theoryrecursion

Let $q_0, q_1, q_2$, . . . be the terms of a continued fraction. Use the recursion relations to determine the continued fraction (as a rational number) for each of the following terms:

$(a) 1, 2, 3, 4$

$(b) 3, 3, 3$

$(c) 3, 3, 3, 3, 3, 3$

The recursion relations are:

$A_n = A_{n-2}+q_n.A_{n-1}$, $A_0 = q_0$

$B_n = B_{n-2}+q_n.B_{n-1}$, $B_0 = 1$

So for part a):

I got $A_0 = 1, A_1 = 3, A_2 = 10, A_3 = 43$ and $B_0 = 1, B_1 = 3, B_2 = 10, B_3=43$. So the continued fraction is $\frac{43}{43}$. Is this correct? And this is how I should do the other parts?

Best Answer

Not quite. The recursive formulas require the previous two terms, and so you need two base cases to start them off. (In other words: how did you decide that $A_1=3$ and $B_1=3$ given the data in your post?)

Here, in addition to $A_0=q_0$ and $B_0=1$, you can use $A_{-1} = 1$ and $B_{-1}=0$. This leads in part (a) to $A_0 = 1, A_1 = 3, A_2 = 10, A_3 = 43$ as you obtained, but instead to $B_0 = 1, B_1 = 2, B_2 = 7, B_3=30$, so that the fraction is $\frac{43}{30}$.

You can check that this is the correct answer by carrying out the Euclidean algorithm on $43$ and $30$ and recording the partial quotients; they are indeed 1, 2, 3, 4.

Related Question