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

  • 0
    Are you going through a book? Can we please have the name of the book?2010-12-26
  • 0
    @Moron: No I am not.2010-12-26
  • 2
    What is the source of these problems then? I am curious (and I suppose other folks are too). Thanks.2010-12-26
  • 0
    @Moron: They are old homework from about a year ago.2010-12-26

1 Answers 1

7

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.