[< ] [^ ] | [> ]
Problem 65: Convergents of $e$
Given the following infinite continued fraction,
$$
\Large a_{0} + \cfrac{b_{1}}{a_{1} + \cfrac{b_{2}}{a_{2} + \cfrac{b_{3}}{\ddots \cfrac{\ddots}{a_{n} + \cfrac{b_{n+1}}{\ddots}}}}}
$$
Let convergents of a continued fraction $A_{n} = x_{n} / y_{n}$ is below:
$$
A_{0} = a_{0} = \frac{x_{0}}{y_{0}}, \ \\
A_{1} = a_{0} + \frac{b_{1}}{a_{1}} = \frac{x_{1}}{y_{1}}, \ \\
A_{2} = a_{0} + \cfrac{b_{1}}{a_{1} + \cfrac{b_{2}}{a_{2}}} = \frac{x_{2}}{y_{2}}, \ \ \dots
$$
By above equations,
$$
\begin{align}
n=0 \ \Rightarrow \ & \begin{cases}
x_{0} = a_{0} \\
y_{0} = 1
\end{cases} \\
n=1 \ \Rightarrow \ & \begin{cases}
x_{1} = a_{0}a_{1} + b_{1} \\
y_{1} = a_{1}
\end{cases} \\
n=2 \ \Rightarrow \ & \begin{cases}
x_{2} = a_{0}a_{1}a_{2} + a_{0}b_{2} + a_{2}b_{1} \\
y_{2} = a_{1}a_{2} + b_{2}
\end{cases}
\end{align}
$$
Then, $A_{2}$ is below:
$$
\begin{align}
A_{2} = \frac{x_{2}}{y_{2}} & = \frac{ a_{0}a_{1}a_{2} + a_{0}b_{2} + a_{2}b_{1} }{ a_{1}a_{2} + b_{2} } \\
& = \frac{ a_{2}(a_{0}a_{1} + b_{1}) + a_{0}b_{2} }{ a_{1}a_{2} + b_{2} } \\
& = \frac{ a_{2}x_{1} + b_{2}x_{0} }{ a_{2}y_{1} + b_{2}y_{0} } \tag{1}
\end{align}
$$
Assume that the following equation $(2)$ holds for $n=k$ , we show it holds when $n = k + 1$ .
$$
A_{n} = \frac{x_{n}}{y_{n}} = \frac{a_{n}x_{n-1} + b_{n}x_{n-2}}{a_{n}y_{n-1} + b_{n}y_{n-2}} \ \ \ \ \text{for} \ n \ge 2 \tag{2}
$$
We already show the equation $(2)$ holds when $n=2$ at the equation $(1)$ .
Since definition of $A_{n}$ , changing $A_{k}$ to $A_{k+1}$ is equivalent to
replacing $a_{k}$ in $A_{k}$ with $a_{k} + \dfrac{b_{k+1}}{a_{k+1}}$ .
$$
\begin{align}
A_{k+1} & = \frac{ ( a_{k} + \frac{b_{k+1}}{a_{k+1}} ) x_{k-1} + b_{k}x_{k-2} }{ ( a_{k} + \frac{b_{k+1}}{a_{k+1}} ) y_{k-1} + b_{k}y_{k-2} } \\
& = \frac{ ( \frac{a_{k}a_{k+1} + b_{k+1}}{a_{k+1}} ) x_{k-1} + b_{k}x_{k-2} }{ ( \frac{a_{k}a_{k+1} + b_{k+1}}{a_{k+1}} ) y_{k-1} + b_{k}y_{k-2} } \\
& = \frac{ (a_{k}a_{k+1} + b_{k+1}) x_{k-1} + a_{k+1}b_{k}x_{k-2} }{ (a_{k}a_{k+1} + b_{k+1}) y_{k-1} + a_{k+1}b_{k}y_{k-2} } \\
& = \frac{ a_{k+1}(a_{k}x_{k-1} + b_{k}x_{k-2}) + b_{k+1}x_{k-1} }{ a_{k+1}(a_{k}x_{k-1} + b_{k}y_{k-2}) + b_{k+1}y_{k-1} } \\
& = \frac{ a_{k+1}x_{k} + b_{k+1}x_{k-1} }{ a_{k+1}y_{k} + b_{k+1}y_{k-1} } \\
& = \frac{x_{k+1}}{y_{k+1}}
\end{align}
$$
Therefore, the equation $(2)$ holds for $n \ge 2$ by induction on n.
Let's get back on track.
The problem statement mentions the Napier's constant $e$ can be written in regular continued fraction.
$$
\begin{align}
e & = [a_{0}; \ a_{1}, \ a_{2}, \ \cdots] \\
& = [2;1,2,1,1,4,1,1,6,1, \dots,1,2k,1, \dots]
\end{align}
$$
Hence, $a_{0} = 2, \ b_{0} = 1$ , and if $n \ge 1$ :
$$
\begin{align}
a_{n} & = \begin{cases}
2 \cdot \left\lceil \dfrac{n}{3} \right\rceil \ \ \ & (n \equiv 2 \ \text{(mod } 3 \text{)}) \\
1 & \text{(others)}
\end{cases} \\
b_{n} & = 1
\end{align}
$$
Therefore, we can compute only numerators using the equation $(2)$ .
$$
\begin{align}
x_{0} & = a_{0} = 2 \\
x_{1} & = a_{0}a_{1} + b_{1} = 2 \cdot 1 + 1 = 3 \\
x_{n} & = a_{n}x_{n-1} + b_{n}x_{n-2} \\
& = a_{n}x_{n-1} + x_{n-2}
\end{align}
$$