combinatorial argument

Question

$\begin{align*} &\text{Prove using combinatorial argument } \\ &1) \qquad \text{For } n \geq k \geq 0 \qquad \left ( n-k \right )\cdot \binom{n}{k} = n \cdot \binom{n-1}{k} \\ &2) \qquad \text{For } n \geq 2 \qquad \quad k \cdot (k-1) \cdot \binom{n}{k} = n \cdot (n-1) \cdot \binom{n-2}{k-2} \\ \end{align*}$

Answer 1

1. mathematically :

$(n-k ). \binom{n}{k} = (n-k). \frac{n!}{(n-k)!k!}$

$= (n-k). \frac{n (n-1)!}{(n-k)(n-k-1)!k!}$

$= \frac{n (n-1)!}{(n-1-k)!k!} = n . \binom{n-1}{ k}$

combinatorial argument:

LHS of the statement counts the number of (x , S) pair such that S is set of choosing a committee of choosing k from n people and x doesnot belong to that committee once committee is formed in $\binom{n}{k}$ then x can be chosen in n-k . RHS counts the same number in another way , first choose a person that will not be included in committee of k people ( n possible ways ) then make the committee from remaining n-1 people .

2. $k . (k-1) .\binom{n}{k } = k . (k-1).\frac{n!}{(n-k)!k!}$

$= k . (k-1).\frac{n . n-1 (n-2)!}{(n-k)!k. (k-1)(k-2)!}$

$= \frac{n . n-1 (n-2)!}{(n-2-(k-2))!(k-2)!}$

$= n.n-1 \binom{n-2}{k-2}$

combinatorial argument:

LHS counts the number of triplet (x,y,S) such that S is set of choosing a committee of choosing k from n people and x and y belongs to that committee, once committee is formed in $\binom{n}{k}$ then for each of these there will be $k$ possibility for x and $k-1$ possibility for y . RHS counts the same number by first choosing x then y then k-2 members of committee , that is $n$ possibility for x , then $n-1$ possibility  for y and then  $\binom{n-2}{k-2}$ ways for remaining k-2 people .

Comments

We've to do using combinatorial argument, not mathematically.

---

thnxs, edited my answer , suggestion are appreciated !