Combinatorial proof of $\sum_{k=1}^n k k!=(n+1)!-1$

Prove: $\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$ (preferably combinatorially)

It's pretty easy to think of a story for the RHS: arrange $n+1$ people in a row and remove the the option of everyone arranged to height from shortest to highest, but it doesn't hold up for the LHS.

Alternatively, trying to visualize the LHS, I noticed that it's like a right angle tetrahedra:

1

2!+2!

3!+3!+3!

...

But it doesn't help to see a connection to the RHS.

Note: no integrals or gamma function nor use of other identities without proving them nor generating functions.

$\sum_{k=1}^n{kk!}$

$=\sum_{k=1}^n{((k+1)-1)k!}$

$=\sum_{k=1}^n{(k+1)k!-k!}$

$=\sum_{k=1}^n{(k+1)!-k!}$

$=(n+1)!-1!$

$=(n+1)!-1$

Given an ordered list of $n+1$ items, pick $k$ between $1$ and $n$. Focus attention on the first $k$ items. Pick one of these items ($k$ ways to do this) to swap with item $k+1$. Now permute this modified initial set of $k$ items ($k!$ ways to do this), and leave unchanged the items past position $k+1$. Each choice of $k$ generates a different collection of permutations. Moreover, as $k$ ranges from $1$ to $n$, we'll generate all possible permutations of the list, except the original list, since the algorithm forces at least one item to move to a new position. Conclude: $$\sum_{k=1}^n kk! = (n+1)! - 1$$

For a permutation $\pi = \pi_1 \ldots \pi_{n+1}$ in $S_{n+1}$, let $m = m(\pi)$ be the maximal index such that $\pi_1 = 1, \pi_2 = 2, \ldots, \pi_m = m$. The number of permutations such that $m(\pi) = m$ for $m < n$ is $(n-m) (n-m)!$: here $n-m$ is the number of choices for $\pi_{m+1} \neq m+1$, and $(n-m)!$ is the number of permutations of the remaining $n-m$ numbers. No permutation satisfies $m(\pi) = n$, and there is a single permutation such that $m(\pi) = n+1$. Altogether, since there are $(n+1)!$ permutations in $S_{n+1}$, $$ (n+1)! = \sum_{m=0}^{n-1} (n-m)(n-m)! + 1 = \sum_{k=1}^n k \cdot k! + 1. $$

You can show $$\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$$ by induction. It holds for $n=1.$ Assume it is satisfied for a given $n$ and show it for $n+1.$ We assume $$\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$$ and we need to show

$$\displaystyle\sum_{k=1}^{n+1} k k!=(n+2)!-1.$$ Just write

$$\displaystyle\sum_{k=1}^{n+1} k k!=\sum_{k=1}^{n} k k!+(n+1)(n+1)!.$$ Use induction hypothesis and you are done.