Preliminaries

First, we write the continued fraction of $e$ in a slightly different form. Instead of $[2,1,2,1,1,4,\ldots],$ we can start the sequence of coefficients

$$[1,0,1,1,2,1,1,4,\ldots]$$

to make the pattern the same throughout. (Everywhere else in this chapter we assume that the partial quotients $a_n$ for $n\geq 1$ are positive, but temporarily relax that condition here and allow $a_1 = 0$ .) The numerators and denominators of the convergents given by this new sequence satisfy a simple recurrence. Using $r_i$ as a stand-in for $p_i$ or $q_i$ , we have

$$r_{3n} =r_{3n-1}+r_{3n-2}$$

$$r_{3n-1} =r_{3n-2}+r_{3n-3}$$

$$r_{3n-2} =2(n-1)r_{3n-3}+r_{3n-4}.$$

Our first goal is to collapse these three recurrences into one recurrence that only makes mention of $r_{3n}$ , $r_{3n-3}$ , and $r_{3n-6}$ . We have

$$r_{3n} =r_{3n-1}+r_{3n-2}$$

$$=(r_{3n-2}+r_{3n-3})+(2(n-1)r_{3n-3}+r_{3n-4})$$

$$=(4n-3)r_{3n-3}+2r_{3n-4}.$$

This same method of simplification also shows us that

$$r_{3n-3}=2r_{3n-7}+(4n-7)r_{3n-6}.$$

To get rid of $2r_{3n-4}$ in the first equation, we make the substitutions

$$2r_{3n-4} =2(r_{3n-5}+r_{3n-6})$$

$$=2((2(n-2)r_{3n-6}+r_{3n-7})+r_{3n-6})$$

$$=(4n-6)r_{3n-6}+2r_{3n-7}.$$

Substituting for $2r_{3n-4}$ and then $2r_{3n-7}$ , we finally have the needed collapsed recurrence,

$$r_{3n}=2(2n-1)r_{3n-3}+r_{3n-6}.$$