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.

How could we prove this ?

$$\sum_{i=1} ^n (i^2+3i+1)\times i!= (n+3) \times (n+1)!-3$$

I did with induction, what I want to know is about other ways to prove this.

share|improve this question
    
I am rolling back @Arturo Magidin's edit,seems descent to me. –  Quixotic Sep 9 '11 at 19:39
    
@Grigory M:I have seen solutions of these kinds of problems using combinatorics,calculus and even elementary number theory.However I don't have any problem if you remove it :-) –  Quixotic Sep 9 '11 at 19:42
    
@ Srivatsan Narayanan:Fixed,my apologies,I somehow forget about that tag. –  Quixotic Sep 9 '11 at 19:47
    
On proofs like this I almost always just start doing induction unless there is a compelling reason not to. –  Tim Seguine Sep 10 '11 at 13:16

4 Answers 4

up vote 10 down vote accepted

We first look at the simpler expression $$\sum_{k=1}^n k\cdot k!.$$ This is $$1\cdot 1!+2\cdot 2! +3\cdot 3!+\cdots +n \cdot n!.$$ In general, $k \cdot k!=(k+1)\cdot k!-k!=(k+1)!-k!$. It follows that the sum above is equal to $$(1!-0!)+(2!-1!)+(3!-2!) +(4!-3!)+\cdots +((n+1)!-n!).$$ Add up. There is a whole lot of cancellation, and we get $(n+1)!-1$.

Now we turn to our problem, which can be rewritten as $$\sum_{k=1}^n(k+1)^2\cdot k! +\sum_{k=1}^n k \cdot k!,$$ since $k^2+3k+1=(k+1)^2+k$. We have already computed the second sum. The first sum is $$\sum_{k=1}^n (k+1)\cdot (k+1)!.$$ The same collapsing argument then shows that this sum is $$(n+2)! -2.$$ Or else we can recycle the previous result, noting that we are dealing with $\sum_{j=2}^{n+1}j\cdot j!$, which is $1$ less than $\sum_{j=1}^{n+1}j\cdot j!$. Finally, add up. We get $$[(n+2)(n+1)!-2] +[(n+1)!-1].$$ This is $(n+3)(n+1)!-3$.

Comment: But the above solution actually does not answer the question! The OP asked that induction not be used. However, induction was used, albeit in a subtle hidden way. We saw the systematic cancellation, it was obvious. But a "proper" complete proof would use the cancellation up to the $k$-th term to prove cancellation up to the $(k+1)$-th term. Much of the time when one sees ellipses ($\dots$) in a mathematical expression, induction is, technically speaking, needed to fill in the full formal details. Not that this should make any practical difference in our mathematical behaviour: Obvious is still obvious.

share|improve this answer
    
(+1)The obvious proof is obvious! –  The Chaz 2.0 Sep 9 '11 at 22:07

I would use $$\sum_{i=1} ^n (i+2)! - i! = (n+2)!+(n+1)! - 2! - 1 !$$

share|improve this answer
    
Note that (i^2+3i+1) = (i+2)(i+1)-1 –  Foo Bah Sep 10 '11 at 0:08
    
@Foo Bah: Indeed. Similarly $(n+2)!+(n+1)! = (n+3)\times(n+1)!$ –  Henry Sep 10 '11 at 0:16

As André Nicolas notes, the essence of the identity is showing that $$\sum_{k=1}^n k \cdot k! = (n+1)! - 1.$$

There's a nice combinatorial proof of this. (See Benjamin and Quinn, Proofs that Really Count, Identity 181 on p. 92.) I'll give it in its $\sum_{k=1}^{n-1} k \cdot k! = n! - 1$ form.

Both sides count the number of permutations of $1, 2, \ldots, n$ that exclude the identity permutation.

The right side is straightforward.

For the left side, how many permutations have $n-k$ as the first number that does not get mapped to itself? There are $k$ choices ($n-k+1, n-k+2, \ldots, n$) for the number that appears in position $n-k$, and then there are $k!$ ways to choose the remaining $k$ numbers to complete the permutation. Adding up over all possible values of $k$ yields the left-hand side.

share|improve this answer
    
I just realized that Eric Naslund gave this combinatorial proof as an answer here. –  Mike Spivey Sep 15 '11 at 3:52

If you observe that $i^2 + 3i + 1 = (i + 2)(i+1) - 1$, then your left-hand sum is $$\sum_{i=1}^n ((i+2)(i +1) - 1)i!$$ $$= \sum_{i=1}^n ((i + 2)! - i!)$$ As Henry noted, this sum telescopes into $$(n + 2)! + (n + 1)! - 2! - 1!$$ $$= (n+2)(n+1)! + (n+1)! - 3$$ $$= (n+3)(n+1)! - 3$$

share|improve this answer

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.