6
$\begingroup$

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.

  • 0
    On proofs like this I almost always just start doing induction unless there is a compelling reason not to.2011-09-10

4 Answers 4

10

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.

5

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

  • 0
    @Foo Bah: Indeed. Similarly $(n+2)!+(n+1)! = (n+3)\times(n+1)!$2011-09-10
4

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.

  • 0
    I just realized that Eric Naslund gave this combinatorial proof as an answer [here](http://math.stackexchange.com/questions/54845/combinatorial-proof-n-1-sum-limits-r-1n-1-r-cdot-r/54848#54848).2011-09-15
3

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$