retagged by
454 views
3 votes
3 votes
$\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*}$
retagged by

1 Answer

1 votes
1 votes

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 .

edited by

Related questions

0 votes
0 votes
0 answers
1
Sahil Gupta asked Nov 23, 2014
721 views
Here's Hockey Stick Identity:what is Hockey Stick Identity means and Where it is used in Practical Application?Also Prove Suitable Explanation of the combinatorial argume...
1 votes
1 votes
0 answers
3
dd asked Jun 26, 2017
208 views
$\begin{align*} &\text{A} = \text{Set of integer sequence }\left ( a_1,a_2,a_2 ,\dots , a_k \right ) \\ &\text{where } 1 \leq a_1 \leq a_2 \leq a_3 \leq \dots \leq a_k \l...
1 votes
1 votes
0 answers
4
dd asked Jun 26, 2017
156 views
Prove that :$\begin{align*} &\text{For n , k , m are integers and } 0 < m \leq k < n \\ &\text{GCD}\left [ \binom{n}{m},\binom{n}{k} \right ] 1 \\ \end{align*}$