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

3 Answers 3

up vote 14 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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