Combinatorial proof involving sum of factorials I need help with this combinatorial proof:
$1\cdot1!+2\cdot2!+\cdots+n\cdot n!=(n+1)!-1$
So far I came up with this:
Let S be a set of numbers $1, 2, \ldots, n+1$
So LHS could be: How many permutations of length $k$ there is over set $S$ such that number $1$ is not the first in permutation. $k$ can be $2, 3,\ldots, n+1$. But the RHS gives me trouble...
Thanks.
(Sorry for the poor formating, I am not good with HTML)  
 A: $n\cdot n!$ counts the number of ways to order $\{1,2,3,\ldots,n+1\}$ without $n+1$ being first. 
$(n-1)\cdot (n-1)!$ counts the number of ways to order $\{1,2,3,\ldots,n+1\}$ with $n+1$ being first and $n$ not second. 
$(n-2)\cdot (n-2)!$ counts the number of ways to order $\{1,2,3,\ldots,n+1\}$ with $n+1$ being first and $n$ second and $n-1$ not third. 
Etc...
The RHS is all the ways to order $\{1,2,3,\ldots,n+1\}$ without all the elements in descending order.
A: We want to show that the permutations of $n+1$ elements, except for one of them, are in bijective correspondence with the pairs $(j,\tau)$ where $\tau$ is a permutation of $k\le n$ elements and $1\le j\le k$, for some $k$.
Here's a correspondence. We start with a permutation $\sigma$ of $\{1,2,3,\ldots,n+1\}$, for example
 i        1 2 3 4 5 6 7 8 9 10
sigma(i)  1 6 3 2 7 5 4 8 9 10

If the permutation is the identity, then it doesn't map anywhere! Otherwise let $k+1$ be the largest index such that $\sigma(k+1)\ne k+1$. In the example $k+1=7$. We have $k\ge 1$ because index $1$ can't be the latest difference between $i$ and $\sigma(i)$.
Let the first output $j$ be the number such that $\sigma(k+1-j)=k+1$. In other words, $j$ is the number of elements to the right of the $k+1$ in the lower line of the permutation, before the trailing sequence of unchanged positions. In the example above we have $j=2$ because the two elements 5 4 come between 7 and the final 8 9 10.
The second output $\tau$ is now defined by $\tau(i) = \begin{cases} \sigma(i) & i < j \\ \sigma(i+1) & i \ge j \end{cases}$
 i      1 2 3 4 5 6
tau(i)  1 6 3 2 5 4

This correspondence is bijective -- we can do it in reverse starting with $(j,\tau)$. First write down $\tau$, then insert the number $k+1$ before the $j$th-to-last element, and finally append the numers $k+2, k+3, \ldots, n+1$ at the end of the permutation.
A: hint: $n\cdot n! = (n+1)!-n!$. Can you continue?
A: Proof by induction works here. This is not a combinatorial proof though (sorry!). 
At $n=1$, the statement $1\cdot 1!=2!-1$ is true; both sides equal $1$.
Assume the statement for $n=k$ is true: $$1\cdot 1!+2\cdot 2!+\cdots+k \cdot k!=(k+1)!-1$$
For $n=k+1$, we have
\begin{align}
1\cdot 1!+2\cdot 2!+\cdots+(k+1) \cdot (k+1)!&=1\cdot 1!+2\cdot 2!+\cdots+k\cdot k!+(k+1) \cdot (k+1)! \\
&=(k+1)!-1+(k+1)\cdot(k+1)! \\
&=(k+1)!(1+(k+1))-1 \\
&=(k+1)!(k+2)-1 \\
&=(k+2)!-1
\end{align}
