# Does this recursive function have a function in terms of n?

I am trying to convert the following recursive function to a non-recursive equation:

$$f(2) = 2$$

For $$n>2$$:

$$f(n)=nf(n-1)+n$$

I have calculated the results for n=2 through to n=9:

\begin{align} f(2)&=2\\ f(3)&=9\\ f(4)&=40\\ f(5)&=205\\ f(6)&=1236\\ f(7)&=8659\\ f(8)&=69280\\ f(9)&=623529 \end{align}

I've tried graphing the function, but have got nowhere

Any help is appreciated!

• oeis.org/A038156 Commented Mar 17, 2019 at 23:01
• @DonThousand a(n) = floor((e-1)*n!) - 1 was exactly what I was looking for. Anyone care to explain how to get that equation? Commented Mar 17, 2019 at 23:12

This is a linear, nonhomogenous recurrence relation. There are general methods to solve it, which you might find in the appropriate courses (I know my combinatorics text goes over it), but here's perhaps a more intuitive derivation.

Notice that you have

$$f(n) = nf(n-1) + n$$

Imagine iterating this several times: that is, we use the definition of $$f$$ for $$f(n-1)$$. We see:

\begin{align} f(n) &= n+ nf(n-1)\\ &= n + n((n-1) + (n-1)f(n-2)) \\ &= n + n(n-1) + n(n-1)f(n-2)\\ &= n + n(n-1) + n(n-1)((n-2) + (n-2)f(n-3)) \\ &= n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2)f(n-3)\\ &= ... \end{align}

If we keep iterating this until we get to our initial condition of $$f(2)=2$$, then we have

$$f(n) = n + n(n-1) + n(n-1)(n-2) + ... + n(n-1)(n-2)...(3)f(2)$$

Take note: since $$f(2) = 2$$, the last term is actually $$n!$$. So what we essentially have is a sum of all of the "falling factorials" of $$n$$ and $$n!$$ itself. (A falling factorial is something like $$9\cdot 8 \cdot 7$$ - it exhibits factorial-like behavior, but doesn't go all of the way to $$2$$ or $$1$$.)

Suppose we factor out $$n!$$ from each term. Then we see

$$f(n) = n! \left( \frac{1}{(n-1)!} + \frac{1}{(n-2)!} + ... + \frac{1}{2!} + \frac{1}{1!} \right)$$

This begs the summation notation:

$$f(n) = n! \left( \sum_{k=1}^{n-1} \frac{1}{k!} \right)$$

This is the summation noted in MachineLearner's answer. Then, leaning on a past MSE post, we get the sequence OP mentioned wanting a derivation of in the comments of their question - an expression involving a floor function and $$e$$:

$$f(n) = n! \left( \sum_{k=1}^{n-1} \frac{1}{k!} \right) = \lfloor n! \cdot (e-1) \rfloor - 1$$

This is derived by simply noting that $$e$$ has the power series

$$e = \sum_{k=0}^\infty \frac{1}{k!}$$

If you start at $$1$$ instead, you get $$e-1$$ since $$1/0!=1$$. The summation in $$f$$ then becomes

$$\sum_{k=1}^{n-1} \frac{1}{k!} = \sum_{k=1}^\infty \frac{1}{k!} - \sum_{k=n}^\infty \frac{1}{k!} = e-1 - \sum_{k=n}^\infty \frac{1}{k!}$$

The remaining summation is less than $$1$$, and thus invites the floor function and the resulting minus one.

And thus, we conclude:

$$f(n) = \lfloor n! \cdot (e-1) \rfloor - 1$$

the expression noted on the OEIS by Don Thousand in the comments.

The general term is given by

$$f(n)= n! \sum_{k=1}^{n-1} \dfrac{1}{k!}=n!\left[e-1+\sum_{k=n}^{\infty}\dfrac{1}{k!} \right]=n!(e-1)+n!\sum_{k=n}^{\infty}\dfrac{1}{k!} .$$

• I feel like this answer would be much more useful to the OP if you explained how you got that equation. Commented Mar 17, 2019 at 23:05