Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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