# For any natural $n$, how could we prove that $\sum\limits_{i=1} ^n (i^2+3i+1) i!= (n+3)(n+1)! - 3$

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.

-
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

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.

-
(+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 !$$

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

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

-