3
$\begingroup$

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!

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

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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!} .$$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .