13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Could you perhaps write it as a telescopic sum? $\endgroup$ – mickep Mar 20 '15 at 18:35
  • $\begingroup$ Your triangle visual suggests one approach: $$n\sum_{k=1}^n k! - \sum_{i=0}^{n-1}\sum_{j=1}^i j!$$ This, together with the telescopic suggestion, shows how the sum really does collapse very neatly. $\endgroup$ – abiessu Mar 20 '15 at 18:36
  • $\begingroup$ @mickep but there are no cancellations as far as I can see. $\endgroup$ – shinzou Mar 20 '15 at 18:37
  • 5
    $\begingroup$ $kk!=(k+1)!-k!$ $\endgroup$ – mickep Mar 20 '15 at 18:37
  • 1
    $\begingroup$ @abiessu I see that the telescopic sum is enough actually. Could you explain how you got to that expression please? $\endgroup$ – shinzou Mar 20 '15 at 18:49
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This interpretation is virtually identical to the one in my answer. $\endgroup$ – Yuval Filmus Mar 21 '15 at 18:16
26
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ +1. This answer gives a more intuitive look at the problem rather than just blindly using induction $\endgroup$ – MCT Mar 20 '15 at 21:40
8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Nice. This should have more upvotes since it actually offers a combinatorial approach! $\endgroup$ – MCT Mar 20 '15 at 21:40
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Note: I realize you said your desired solution is a combinatorial one, but I thought I would provide a complete induction proof in case you did not get any sort of combinatorial answers.

Claim: For all $n\geq 1, \sum_{k=1}^n kk! = (n+1)!-1$.

Proof. Let $S(n)$ denote the statement $$ S(n) : \sum_{k=1}^n kk! = (n+1)!-1. $$ Base step ($n=1$): $S(1)$ is true because $1=2!-1$.

Inductive step: For some fixed $\ell\geq 1$, assume the inductive hypothesis $S(\ell)$ to be true where $$ S(\ell) : \sum_{k=1}^\ell kk! = (\ell+1)!-1. $$ To be shown is that $S(\ell+1)$ follows, where $$ S(\ell+1) : \sum_{k=1}^{\ell+1} kk! = (\ell+2)!-1. $$ Starting with the left-hand side of $S(\ell+1)$, \begin{align} \sum_{k=1}^{\ell+1} kk! &= \sum_{k=1}^\ell kk! + (\ell+1)(\ell+1)!\tag{by definition of $\Sigma$}\\[1em] &= [(\ell+1)!-1]+(\ell+1)(\ell+1)!\tag{by $S(\ell)$}\\[1em] &= (\ell+1)!(1+\ell+1)-1\\[1em] &= (\ell+2)\cdot(\ell+1)!-1\\[1em] &= (\ell+2)!-1, \end{align} we see that the right-hand side of $S(\ell+1)$ follows. This completes the inductive step.

Thus, by mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. $\blacksquare$

$\endgroup$
1
$\begingroup$

Using some expansion and recombining tricks, we can evaluate this sum like so:

$$\sum_{k=1}^n kk! = 1! + (2! + 2!) + (3! + 3! + 3!) + \dots\\ =\sum_{k=1}^n k! + \sum_{k=2}^n k! + \sum_{k=3}^n k!\dots\\ =n\sum_{k=1}^n k! - 1! - (1! + 2!) - (1! + 2! + 3!) - \dots - (1! + 2! + \dots + (n-1)!)\\ =n\sum_{k=1}^n k! - \sum_{k=1}^{n-1}\sum_{j=1}^k j!$$

Reversing the order of things, we have

$$n\sum_{k=1}^n k! - \sum_{k=1}^{n-1}\sum_{j=1}^k j!=nn! + n(n-1)! + n(n-2)!+\dots - (n-1)! - 2(n-2)! - \dots - (n-1)1!\\ =(n+1)n!+(n-2)! + n(n-3)! + n(n-4)! + \dots - 2(n-2)! - 3(n-3)! -\dots -n +1\\ =(n+1)!+2(n-3)!+n(n-4)!+n(n-5)!+\dots -3(n-3)!-4(n-3)!-\dots-n+1\\ \vdots\\ =(n+1)!+(n-2)1!-(n-1)1!=(n+1)!-1$$

This collapse is obviously much messier than the telescoping mentioned elsewhere, but nevertheless works out correctly.

$\endgroup$
1
$\begingroup$

Let $S$ be the set of all permutations f of ${1,2,3,..,, n+1}$ with at least one non-fixed point (i.e., a value k with $f(k)≠k$). Then $|S| = (n+1)!-1$.

Now count the permutations with the highest non-fixed point first, then those with the 2nd highest non-fixed point (which are not already counted), then those with the 3rd highest non-fixed point (which are not already counted), and so on. Below are the details.

Let $S[n+1]$ be the set of permutations with $n+1$ as a non-fixed point. For each $k < n+1$, define $S[k]$ to be the set of all permutations in $S - (S[n+1] ∪ S[n] ∪ ... ∪ S[k+1])$ with $k$ as a non-fixed point. Then

$|S[n+1]|= n.n!$ because there are $n.n!$ permutations with $f(n+1)≠n+1$. [Just take any particular permutation of ${1,2,3,..,n}$ and insert $n+1$ in any of the first $n$ spaces (of the $n+1$ spaces) created by the permutation to get $n$ such permutations from it.]

$|S[n]|=(n-1).(n-1)!$ because there are $(n-1).(n-1)!$ permutations with $f(n+1)=n+1$ and $f(n)≠n$.

$|S[n-1]| = (n-2).(n-2)!$ because there are $(n-2).(n-2)!$ permutations with $f(n+1)=n+1$, $f(n)=n$, and $f(n-1)≠n-1$.

$|S[n-2]|=(n-3).(n-3)!$ because there are $(n-3).(n-3)!$ permutations with $f(n+1)=n+1$, $f(n)=n$, $f(n-1)=n-1$, and $f(n-2)≠n-2$.
. . . .
$|S[3]|=2.(2!)$ because there are $2.(2!)$ permutations with $f(n+1)=n+1$, $f(n)=n$, $f(n-1)=n-1$, $\cdots$, $f(4)=4$, and $f(3)≠3$.

$|S[2]|=1.(1!)$ because there are $1.(1!)$ permutations with $f(n+1)=n+1$, $f(n)=n$, $f(n-1)=n-1$, $\cdots$, $f(4)=4$, $f(3)=3$, and $f(2)≠2$.

$|S[1]|=0$ because there are $(0).(0!)$ permutations with $f(n+1)=n+1$, $f(n)=n$, $f(n-1)=n-1$, $\cdots$, $f(4)=4$, $f(3)=3$, $f(2)=2$, and $f(1)≠1$.

So we get $(n+1)!-1 = |S|$
$= |S[n+1]| + |S[n]| + |S[n-1]| + ... + |S[3]| + |S[2]|$
$= n.n! + (n-1).(n-1)! + (n-2).(n-2)! + ... + 2.(2!) +1.(1!)$. QED

$\endgroup$
  • 1
    $\begingroup$ @ Watson - Is this how a first-time user is welcomed? By the way, I don't know how to use MathJax. Disculpame. Thanks anyway. $\endgroup$ – Ram Jul 22 '16 at 10:35
  • $\begingroup$ Sorry for being a bit rude in my previous comment. I should have given you this link for MathJax. This is really useful on this site. Anyway, welcome to Math.SE! $\endgroup$ – Watson Jul 22 '16 at 11:08
0
$\begingroup$

By induction on $n$.

Assume that: $$\sum_{k=1}^{n}kk! = (n+1)! - 1$$

We have:

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

$\endgroup$
0
$\begingroup$

The factorial function is defined recursively by

$\tag 1 (n+1)! = (n+1)\, n!$

We know that the number of permutations of a set $X$ with $n$ elements is equal to $n!$. Moreover, a simple combinatorial [fixed point or not fixed point]-argument (see next section) can be used to alternatively confirm $\text{(1)}$ by counting permutations,

$\tag 2 (n+1)! = n \, n! + n!$

You can repeat/descend on this combinatorial argument and for $n \ge 1$ write

$\tag 3 \displaystyle (n+1)! = \big [\sum_{k=m}^n k \, k! \, \big ] + m!, \text{ with } 1 \le m \le n$

and letting $m = 1$,

$\tag 3 \displaystyle (n+1)! = \big [ \sum_{k=1}^n k \, k! \, \big ] + 1!, \text{ with } 1 \le m \le n$


Let $\mathtt S$ denote the set of all bijections $\sigma$ of the set of integers $\{1,2,\dots,n\}$.

Let $\mathtt T$ denote the bijections $\tau$ of the set of integers $\{1,2,\dots,n+1\}$ such that $\tau(n+1) \ne n+1$.

Let $\mathtt U = \{1,2,\dots,n\} \times \mathtt S$.

We can put $\mathtt U$ in bijective correspondence with $\mathtt T$ by the mapping

$\tag 4 (k, \sigma) \mapsto \sigma' \circ \big(k \; t\big), \; \text{ with } t = n+1 \text{ and transposition } \big(k \; t\big)$

Note that in $\text{(4)}$ we extend the domain of $\sigma$ by defining $\sigma'(t) = t$.

This mapping is injective. If $\tau \in \mathtt T$ and $k = \tau^{-1}(t)$ then $t$ is a fixed point of $\tau \circ \big(k \; t\big)$ so the mapping is also surjective.

The set of permutations of $\{1,2,\dots,n+1\}$ leaving $n+1$ fixed can be identified with the set $\mathtt S$.

Thus by partitioning the bijections into two blocks, we conclude that $\text{(2)}$ is true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.