# Summation involving a factorial: $1 + \sum_{j=1}^{n} j!j$ [duplicate]

$$1 + \sum_{j=1}^{n} j!j$$

I want to find a formula for the above and then prove it by induction. The answer according to Wolfram is $(n+1)!-1$, however I have no idea how to get there. Any hints or ideas on how I should tackle this one?

-

## marked as duplicate by ᴡᴏʀᴅs, rogerl, vociferous_rutabaga, J. W. Perry, Jack D'AurizioOct 11 '14 at 23:49

This is a simple induction. Use $(n+1)! = (n+1) \cdot n! = n\cdot n! + n!$.

Added: I don't see any better way than to play around with the formula. Rearrange this and you have $j \cdot j! = (j+1)! - j!$. But then you have \begin{align*} \sum_{j=1}^{n} j \cdot j! & = \sum_{j=1}^{n} [ (j+1)! - j!] \\ & = [2! - 1!] + [3! - 2!] + \cdots + [n! - (n-1)!] + [(n+1)! - n!] \end{align*} and you see that everything cancels, except the terms $- 1!$ from the first summand and $(n+1)!$ from the last summand, hence the sum must be equal to $(n+1)! - 1$.

Edit 2

Here's the argument: We want to prove that the following statement $T(n)$ holds for all $n \in \mathbb{N}$: $(n+1)! - 1 = \sum_{j=1}^{n} j \cdot j!.$ For $n = 1$ we have the statement $T(1)$: $1 = (1+1)! - 1 = \sum_{j=1}^{1} j \cdot j! = 1\cdot 1! = 1,$ so this is ok. Assume that $T(n)$ holds. We want to prove $T(n+1)$: $(n+2)! - 1 = \sum_{j=1}^{n+1} j \cdot j!.$ Start with the right hand side: $\sum_{j=1}^{n+1} j \cdot j! = (n+1)\cdot (n+1)! + \sum_{j=1}^{n} j \cdot j!$ But the last sum is equal to $(n+1)! - 1$ by our assumption that $T(n)$ is true, so \begin{align*} \sum_{j=1}^{n+1} j \cdot j! & = (n+1)\cdot (n+1)! + (n+1)! - 1 \\ & = [(n+1) + 1]\cdot(n+1)! - 1 = (n+2) \cdot (n+1)! - 1\\ & = (n+2)! - 1, \end{align*} so $T(n+1)$ holds as well.

-
Well I havent gotten to the induction part yet. First I need to find a formula for it. I have the answer, but I dont have the steps. I need to know how to do it on my own.. – maq Jan 22 '11 at 22:58
How did you figure that $j*j!=(j+1)!-j!$ ? – maq Jan 22 '11 at 23:15
@mohabitar: I don't really know. I played around with the factorials. From my first line: $(j+1)! = j \cdot j! + j!$ and hence $j \cdot j! = (j+1)! - j!$. – t.b. Jan 22 '11 at 23:29
@Theo so now that we have the formula, I dont get how we prove it by induction. So we say that T(n)=(n+1)! (get rid of the -1 since the original problem had a +1 after the summation). So then we need to show that T(n+1)=(n+2)! ? I dont get how I would prove that.. – maq Jan 23 '11 at 0:29
@mohabitar: Don't get rid of the $-1$! We have \begin{align*} (n+2)! - 1 = (n+1)\cdot (n+1)! + ((n+1)! - 1) = (n+1)\cdot (n+1)! + \cdots \end{align*} where you fill in the $\cdots$ using the induction hypothesis! – t.b. Jan 23 '11 at 0:32

There is a nice interpretation of this identity in terms of uniqueness of representation in factorial base. But to answer your comment to Theo Buehler's answer, telescoping sequences are just a thing that you should be aware of and try to look for, and the identity Theo used is actually equivalent to what Wolfram told you, so...

-
Thanks for that, I was sure you'd have a good explanation for the identity! – t.b. Jan 22 '11 at 23:54

It looks like you have a closed form already. If you want to derive it rather than get it from an oracle, Gosper's algorithm will do the job.

-
Or rather the instructions were to find a formula. Not sure if that means the same thing.. – maq Jan 22 '11 at 22:57