Explicit closed formulas for A056542 and A079751?

Question

Consider the recurrence $B_1 = 0$, $B_n = nB_{n-1} + 1$ for $n\ge 1$ as defined by http://oeis.org/A056542 or by R. Sedgewick, Permutation generation methods, Computing Surveys, 9 (1977), 137–164. How do we prove that $B_n=\lfloor n!(e-2)\rfloor $ ? I followed Sedgewick's presentation until and including his derivation $$B_n\ =\ n!\sum_{2\le k\le n}\frac{1}{k!}\tag{*}\ ;$$ this formula is clear to me. After this, the author says that it's easily verified that $$B_n\ =\ \lfloor n!(e-2)\rfloor\tag{**}\,,$$ referencing the series expansion $e=\sum_{k\ge 0}\frac{1}{k!}$.

So, how do we actually prove (**) from (*) ?

---

Similarly, consider the recurrence relation $a_3=0$, $a_n=na_{n-1}+1$ for $n\ge 4$. The Web site https://oeis.org/A079751 says that $$a_n = \lfloor c\cdot n!\rfloor\qquad(n\ge 3)\tag{***}$$ where $c = \lim_{n\to\infty} \frac{a_n}{n!} = 0.05161516179237856869$. How do we prove the existence of the limit and (***) ?

Answer 1

Fix a non-negative integer $m$, and let $a_n$ satisfy

$$ a_m = 0, \qquad a_n = na_{n-1} + 1 \quad \text{for} \quad n \geq m+1. $$

(OP's cases correspond to $m = 1$ and $m = 3$, respectively.) Then its exponential generating function $f(x) = \sum_{n=m}^{\infty} \frac{a_n}{n!}x^n$ satisfies

$$ f(x) = \sum_{n=m+1}^{\infty} \frac{a_n}{n!}x^{n} = \sum_{n=m+1}^{\infty} \frac{na_{n-1}+1}{n!}x^{n} = xf(x) + \sum_{n=m+1}^{\infty} \frac{x^n}{n!}. $$

From this, we get

$$ f(x) = \frac{1}{1-x}\sum_{n=m+1}^{\infty} \frac{x^n}{n!} = \left(\sum_{n\ge 0}x^n\right)\left(\sum_{n\ge m+1}\frac{x^n}{n!}\right) = \sum_{n=m+1}^{\infty} \left( \sum_{k=m+1}^{n} \frac{1}{k!} \right) x^n $$

and hence

$$ a_n = n! \sum_{k=m+1}^{n} \frac{1}{k!}. $$

Now let $c = \sum_{k=m+1}^{\infty} \frac{1}{k!} = e - \sum_{k=0}^{m} \frac{1}{k!}$. Then

• $\displaystyle\lim_{n\to\infty} \frac{a_n}{n!} = c$

• $n!c \geq a_n$.

• For $n \geq m$,

  $$ n!c - a_n = \sum_{k=n+1}^{\infty} \frac{n!}{k!} < \sum_{k=n+1}^{\infty} \frac{1}{(n+1)^{k-n}} = \frac{1}{n} \leq 1, $$

  and so, $n!c < a_n + 1$.

Combining these altogether, it follows that

$$ \lfloor n!c \rfloor = a_n \quad\text{for} \quad n \geq m. $$

Answer 2

Note that if we keep summing to infinity the series in $(*)$ sums to $e-2$ because it is the series for $e^1$ less the $\frac 1{0!}$ and $\frac 1{1!}$ terms. Now in $$\sum_{2}^\infty\frac{n!}{k!}\tag{*}$$ note that all the terms up to $n$ are integral and all the terms after $n$ are fractions that sum to less than $1$. The infinite sum is then $n!(e-2)$ and deleting the terms after $n$ is handled by rounding down.