Reccursive formula as a non-recursive

Question

The recursive formula is give as follows:

$$ s_n = n s_{n-1} + (n-1)!$$ and $s_2 = 1$. How to construct a non-recursive formula?

Answer 1

By working out the first few cases, you observe that the sequence satisfies $$s_n=n!(s_0+H_n)\,,$$ where $H_n=\sum_{k=1}^n\frac{1}{k}$ is the $n$th harmonic number. One can then confirm that it is indeed the case by observing that $$s_{n+1}=(n+1)s_n+n!=(n+1)!(s_0+H_n)+n!=(n+1)!\left(s_0+H_n+\frac{1}{n+1}\right)=(n+1)!(s_0+H_{n+1})\,.$$ You can obtain your particular sequence by substituting the appropriate value for $s_0$.

Answer 2

Dividing by $n!$,

$$\frac{s_n}{n!}=\frac{s_{n-1}}{(n-1)!}+\frac1n,$$

which we can write

$$h_n=h_{n-1}+\frac1n.$$

So obviously

$$h_n=H_n+h_0$$ and $$s_n=n!(H_n+h_0)=n!(H_n+s_0).$$

---

Unfortunately, there is no shortcut to computing the Harmonic numbers exactly, so this result is not much better than the initial recursion.

Answer 3

The relation is equivalent to $$s_{n+1}=(n+1)s_n+n!,~~s_1=1$$ Let $$s_n=u_n\times n!$$ $$\implies u_{n+1}\times (n+1)!=(n+1)\times u_n\times n!+n!, ~~~~u_1=1$$ $$\implies (n+1)u_{n+1}=(n+1)u_n+1,~~~u_1=1$$ $$u_{n+1}=u_n+\frac{1}{n+1}$$ This is essentially the relation for the harmonic numbers, which don't have any simple closed form.

It'd be SO much easier to solve if we had $$\implies (n+1)u_{n+1}=(n+2)u_{n+1}+1$$ instead (see Solve $(n+1)t_{n+1}=(n+2)t_n+1$, $t_1=1$):( Are you sure it's not that, ie are you certain your relation shouldn't be $$s_{n+1}=(n+2)s_n+n!,~~s_1=1$$