Please give a DETAILED response!! Thanks. 1. Find a proof of Theorem 1 using the
ID: 2987134 • Letter: P
Question
Please give a DETAILED response!! Thanks.
1. Find a proof of Theorem 1 using the algebraic formula for (n choose k) and use a proof of Theorem 2, using the combinatorial meaning of both sides.
Theorem 1 : The number of ordered k-element subsets of a set with n elements is n(n-1)...(n-k+1)
Theorem 2 : The number of k-subsets of an n-set is (n(n-1)...(n-k+1) / k!) = (n! / k!(n-k)!)
2. Prove that (n choose 2) + (n+1 choose 2) = n^2; give two proofs, one using the combinatorial interpretation, and the other using the algebraic formula for the binomial coefficients.
3. Prove in two ways that (n choose k) = (n/k)(n-1 choose k-1)
I would greatly appreciate any help and understanding of formulating these proofs! I am lost. Thanks!!
Explanation / Answer
Theorem 1:
The reason for the name will be clear a bit later. But for now let