Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$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?

share|improve this question

marked as duplicate by Behaviour, rogerl, Morgan O, J. W. Perry, Jack D'Aurizio Oct 11 at 23:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3 Answers 3

up vote 15 down vote accepted

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.

share|improve this answer
    
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...

share|improve this answer
    
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.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.