1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Winther Apr 21 at 14:08
2
$\begingroup$

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} $$

$\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.