5
$\begingroup$

Show that $\displaystyle 1+ \sum\limits_{k=1}^{n} k \cdot k! = (n+1)!$

RHS: This is the number of permutations of an $n+1$ element set. We can rewrite this as $n!(n+1)$.

LHS: It seems that the $k \cdot k!$ has a similar form to $(n+1)! = (n+1)n!$ Also we can write $1 = 0!$ I think you use the mulitplication principle is being used here (e.g. the permutations of a $k$ element set multiplied by $k$).

Note that a combinatorial proof is wanted (not an algebraic one).

$\endgroup$
  • $\begingroup$ Are you going through a book? Can we please have the name of the book? $\endgroup$ – Aryabhata Dec 26 '10 at 18:53
  • $\begingroup$ @Moron: No I am not. $\endgroup$ – PrimeNumber Dec 26 '10 at 18:58
  • 2
    $\begingroup$ What is the source of these problems then? I am curious (and I suppose other folks are too). Thanks. $\endgroup$ – Aryabhata Dec 26 '10 at 19:08
  • $\begingroup$ @Moron: They are old homework from about a year ago. $\endgroup$ – PrimeNumber Dec 26 '10 at 19:44
7
$\begingroup$

Here is a brief description of one combinatorial way to approach this. Suppose we are permuting $\{1,2,3,\ldots,n+1\}$. One permutation is $P=(1,2,3,\ldots,n+1)$. Any other permutation has a first position from the left which differs from $P$.

Let $S_1$ be the set of permutations that first differs from $P$ in position $n$. Let $S_2$ be the set of permutations that first differs from $P$ in position $n-1$. Continue this until we get to $S_n$, which is the set of permutations that first differs from $P$ in position $1$.

When we count the size of $S_i$, we can convince ourselves that it is $(i+1)!-i! = i \cdot i!$. This is the part I'm skipping over. Also counting $P$ then gives us the left hand side.

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