8
$\begingroup$

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

3 Answers 3

16

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.

  • 0
    @mohabitar: Sorry, there was a typo in my last post, there should have been $(n+1)\cdot(n+1)!$ instead of $(n+1)n!$.2011-01-23
4

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...

  • 0
    Thanks for that, I was sure you'd have a good explanation for the identity!2011-01-22
0

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.

  • 0
    Or rather the instructions were to find a formula. Not sure if that means the same thing..2011-01-22