# Give a closed formula for the recursive series of $S_1 = \frac{a_1}{b_1}, S_{n+1} = \frac{a_{n+1}}{b_{n+1}+S_n}$

## The Problem:

The following real numbers are given:

$$a_1,a_2,a_3,...\in\Bbb{R}\backslash\{0\} \\ b_1,b_2,b_3,...\in\Bbb{R}\backslash\{0\}$$

We define a recursive series of:

$$S_1 = \frac{a_1}{b_1} \\ \forall n \in \Bbb{N}^+: \quad S_{n+1} = \frac{a_{n+1}}{b_{n+1}+S_n}$$

What's the closed formula for $$S_n$$, which includes the values of $$a_1,...,a_n$$ and $$b_1,...,b_n$$?

## My attempt:

Assuming that $$S_n$$ can be written up as

$$S_n = \frac{a_{\text{old}}}{b_{\text{old}}}$$

We can deduce that

$$S_{n+1} = \frac{a_{n+1}}{b_{n+1}+\frac{a_{\text{old}}}{b_{\text{old}}}} = \frac{a_{n+1}}{\frac{b_{n+1}b_{\text{old}}+a_{\text{old}}}{b_{old}}} = \frac{a_{n+1}b_{\text{old}}}{b_{n+1}b_{\text{old}}+a_{\text{old}}} = \frac{a_{\text{new}}}{b_{\text{new}}} \ \ (*)$$

So if $$S_n$$ can be written as a simple fraction, $$S_{n+1}$$ can too. Since $$S_1$$ is a simple fraction, all $$S_i$$ can be written as simple fractions, and the above formula gives us the way to do so.

At this point, I wrote up the first $$5$$ members of the $$S$$ series:

$$S_1 = \frac{a_1}{b_1} \\ S_2 = \frac{a_2}{b_2+\frac{a_1}{b_1}} \stackrel{(*)}{=} \frac{a_2b_1}{b_2b_1+a_1} \\ S_3 = \frac{a_3}{b_3+\frac{a_2}{b_2+\frac{a_1}{b_1}}} \stackrel{(*)}{=} \frac{a_3b_2b_1+a_3a_1}{b_3b_2b_1+b_3a_1+a_2b_1} \\ S_4 = \frac{a_4}{b_4+\frac{a_3}{b_3+\frac{a_2}{b_2+\frac{a_1}{b_1}}}} \stackrel{(*)}{=} \frac{a_4b_3b_2b_1+a_4b_3a_1+a_4a_2b_1}{b_4b_3b_2b_1+b_4b_3a_1+b_4a_2b_1+a_3b_2b_1+a_3a_1} \\ S_5 = \frac{a_5}{b_5+\frac{a_4}{b_4+\frac{a_3}{b_3+\frac{a_2}{b_2+\frac{a_1}{b_1}}}}} \stackrel{(*)}{=} \\ \stackrel{(*)}{=} \frac{\begin{matrix}a_5b_4b_3b_2b_1+a_5b_4b_3b_1+a_5b_4a_2b_1+ \\ +a_5b_4a_2b_1+a_5a_3b_2b_1+a_5a_3a_1\end{matrix}}{ \begin{matrix}b_5b_4b_3b_2b_1+b_5b_4b_3b_1+b_5b_3a_2b_1+b_5a_3b_2b_1+ \\ +b_5a_3a_1+a_4b_3b_2a_1+a_4b_3a_1+a_4a_2b_1\end{matrix}}$$

I can definitely see some structure, but it becomes chaotic after a while. It would be incredible if we were to come up with a formula like:

$$S_n = \frac{\sum(\prod f(a_n;a_{n-1},b_{n-1},\dots,a_1,b_1))}{\sum(\prod f(b_n;a_{n-1},b_{n-1},\dots,a_1,b_1)))+\sum(\prod g(a_{n-1},b_{n-1},\dots,a_1,b_1))}$$

Where I intentionally used the same $$f$$ twice, since the beginning of the denominator is exactly the same as swapping $$a_n$$ in the numerator for $$b_n$$.

If we were to obtain such a formula, it wouldn't be difficult to prove its validity by induction. So any help would be appreciated!

• There is no useful closed formula like this. To compute $S_n$ using the recursion you only require $n$ additions and $n$ divisions. A closed formula like the one you seek will be much more complicated and require many many more additions and multiplications/divisions. – Winther Apr 21 at 14:08

## 1 Answer

What you have is an iterated composition according to the terminology of Dixon J. Jones, A chronology of continued square roots and other continued compositions, through the year 2016 in contrast to a similar continued composition which would be a continued fraction in this case. The Wikipedia article Continued fraction has some indication of using products of $$2\times 2$$ matrices to compute convergents. This seems to be the best way to proceed. Define the sequence of matrices $$M_n := \begin{bmatrix} 0 & 1 \\ a_n & b_n \end{bmatrix}. \tag{1}$$ and the sequence of matrix products $$P_n := \begin{bmatrix} u_n & v_n \end{bmatrix} := \begin{bmatrix} 0 & 1 \end{bmatrix} \; \prod_{k=1}^n M_k . \tag{2}$$ with $$\ S_n = u_n/v_n\$$ which is the closed formula you wanted.

By the way, if the we use the matrix transpose $$\ M_n^\top\$$ of the $$\ M_n\$$ and multiply on the right with $$\ [^{0}_{1}],\$$ then we get continued fractions instead of iterated fractions.

An alternative approach comes from the Wikipedia article Continuant. Given the sequence of tridiagonal determinants $$d_0 := 1, \; d_1 := \mid b_1\mid, \; d_2 := \begin{vmatrix} b_1 & -a_1 \\ 1 & b_2 \end{vmatrix}, \; d_3 := \begin{vmatrix} b_1 & -a_1 & 0 \\ 1 & b_2 & -a_2 \\ 0 & 1 & b_3 \end{vmatrix},\ \dots, \tag{3}$$ then the sequence $$\ S_n = a_n\ d_{n-1}/d_n.\$$ The determinants satisfy the recursion equation $$d_{n+1} = b_{n+1}\ d_n + a_n\ d_{n-1}. \tag{4}$$