Show that 1+∑_(k=1)^n k⋅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⋅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).

Rohan Mcpherson

Rohan Mcpherson

Answered question

2022-09-30

Show that 1 + k = 1 n k 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 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).

Answer & Explanation

Ufumanaxi

Ufumanaxi

Beginner2022-10-01Added 5 answers

Here is a brief description of one combinatorial way to approach this. Suppose we are permuting { 1 , 2 , 3 , , n + 1 }. One permutation is P = ( 1 , 2 , 3 , , 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 i !. Also counting P then gives us the left hand side.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?