Monday, August 21, 2017

An easy exercise on continued fractions

1. Basic theory of continued fractions

Let $(a_n)_{n\geq0}$ and $(b_n)_{n\geq1}$ be such that $a_n, b_n > 0$. (By convention, we always set $b_{0} = 1$.) If we define $2\times 2$ matrices $(P_n)_{n\geq-1}$ by

$$ P_n = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_0 \end{pmatrix} \begin{pmatrix} 0 & b_1 \\ 1 & a_1 \end{pmatrix} \cdots \begin{pmatrix} 0 & b_n \\ 1 & a_n \end{pmatrix} $$

then it can be written in the form

$$ P_n = \begin{pmatrix} p_{n-1} & p_n \\ q_{n-1} & q_n \end{pmatrix} $$

where $(p_n)$ and $(q_n)$ solves the following recurrence relation

$$ \begin{cases} p_n = a_n p_{n-1} + b_n p_{n-2}, & p_{-2} = 0, p_{-1} = 1 \\ q_n = a_n q_{n-1} + b_n q_{n-2}, & p_{-2} = 1, p_{-1} = 0 \end{cases} $$

Using the theory of fractional linear transformation, we find that

$$ \frac{p_n}{q_n} = a_0 + \mathop{\vcenter{\Large\mathrm{K}}}_{i=1}^{n} \frac{b_i}{a_i} = a_0 + \dfrac{b_1}{a_1 + \dfrac{b_2 }{a_2 + \dfrac{\ddots }{\ddots \dfrac{b_{n-1}}{a_{n-1} + \dfrac{b_n}{a_n} } }}} $$

where the right-hand side is the Gauss' Kettenbruch notation for continued fractions. Taking determinant to $P_n$ and simplifying a little bit, we also obtain

$$ \frac{p_n}{q_n} = a_0 + \sum_{i=1}^{n} (-1)^{i-1} \frac{b_1 \cdots b_i}{q_iq_{i-1}} $$

which is often useful for establishing the convergence of the infinite continued fraction.

2. Computing some continued fractions

Let $(p_n)$ and $(q_n)$ be as before. Assume that $p_n/q_n$ converges and that we can find a sequence $(r_n)$ of positive reals such that $\sum_{n=0}^{\infty} \frac{q_n}{r_n} x^n$ converges for $x \in [0, 1)$ and diverges at $x = 1$. Then we can compute the limit of $p_n/q_n$ through the following averaging argument:

$$ a_0 + \mathop{\vcenter{\Large\mathrm{K}}}_{i=1}^{\infty} \frac{b_i}{a_i} = \lim_{n\to\infty} \frac{p_n}{q_n} = \lim_{n\to\infty} \frac{p_n / r_n}{q_n / r_n} = \lim_{x \to 1^-} \frac{\sum_{n=0}^{\infty} \frac{p_n}{r_n} x^n}{\sum_{n=0}^{\infty} \frac{q_n}{r_n} x^n}. $$

We give some examples to which this technique applies.

Example 1. As the first example, we consider the following identity

$$ \dfrac{1}{1 + \dfrac{2}{2 + \dfrac{3}{3 + \ddots}}} = \mathop{\vcenter{\Large\mathrm{K}}}_{n=1}^{\infty} \frac{n}{n} = \frac{1}{e-1}. $$

In this case, it turns out that we can choose $r_n = n!$. Indeed, assume that $(c_n)$ solves the recurrence relation $c_n = n c_{n-1} + n c_{n-2}$. Then the exponential generating function

$$ y(x) = \sum_{n=0}^{\infty} \frac{c_n}{n!} x^n $$

solves the initial value problem

$$ y' + \frac{x^2+1}{x(x-1)} y = \frac{c_0}{x(x-1)}, \qquad y(0) = c_0. $$

The solution is easily found by the integrating factor method.

$$ y(x) = \frac{c_0 + (c_1 - 2c_0)x e^{-x}}{(x-1)^2}. $$

Plugging $c_n = p_n$ and $c_n = q_n$, we obtain

$$ \mathop{\vcenter{\Large\mathrm{K}}}_{n=1}^{\infty} \frac{n}{n} = \lim_{x \to 1^-} \frac{p_0 + (p_1 - 2p_0)x e^{-x}}{q_0 + (q_1 - 2q_0)x e^{-x}} = \frac{e^{-1}}{1 - e^{-1}} = \frac{1}{e-1} $$

as desired.

Example 2. The exponential generating function $y(x)$ of $c_n = nc_{n-1} + nc_{n-2}$ solves the equation

$$ (x-1)y'' + 2y' + y = 0. $$

Any solution of this equation is of the form

$$ y(x) = \frac{\alpha I_1(2\sqrt{1-x}) + \beta K_1(2\sqrt{1-x})}{\sqrt{1-x}}, $$

where $I_1$ and $K_1$ are the modified Bessel functions of order 1. From this we deduce that

$$ \dfrac{1}{1 + \dfrac{1}{2 + \dfrac{1}{3 + \ddots}}} = \mathop{\vcenter{\Large\mathrm{K}}}_{n=1}^{\infty} \frac{1}{n} = \lim_{x \to 1^-} \frac{I_1(2) K_1(2\sqrt{1-x}) - K_1(2) I_1(2\sqrt{1-x})}{I_0(2) K_1(2\sqrt{1-x}) + K_0(2) I_1(2\sqrt{1-x})} = \frac{I_1(2)}{I_0(2)}. $$

Example 3. Consider the Rogers-Ramanujan continued fraction

$$ \dfrac{1}{1 + \dfrac{q}{1 + \dfrac{q^2}{1 + \ddots}}} = \mathop{\vcenter{\Large\mathrm{K}}}_{n=1}^{\infty} \frac{q^{n-1}}{1}. $$

Adopting the same strategy, the generating function $y(x) = \sum_{n=0}^{\infty} c_n x^n$ for the recurrence relation $c_n = c_{n-1} + q^{n-1} c_{n-2}$ satisfies

$$ y(x) = c_0 + \frac{c_1 x}{1-x} + \frac{qx^2}{1-x} y(qx). $$

Let $y_0$ be the solution for $(c_0, c_1) = (0, 1)$ and $y_1$ the solution for $(c_0, c_1) = (1, 1)$. Then it follows that both $y_0$ and $y_1$ has simple pole at $x = 1$ and thus

$$ \mathop{\vcenter{\Large\mathrm{K}}}_{n=1}^{\infty} \frac{q^{n-1}}{1} = \frac{1 + q y_0(q)}{1 + q y_1(q)}. $$

Iterating the functional equation for $y_0$ and $y_1$, we find that

$$ 1 + qy_0(q) = \sum_{n=0}^{\infty} \frac{q^{n(n+1)}}{(q;q)_n}, \qquad 1 + qy_1(q) = \sum_{n=0}^{\infty} \frac{q^{n^2}}{(q;q)_n}. $$

Rogers-Ramanujan identities tell that these can be represented in terms of infinite $q$-Pochhammer symbol.