Saturday 28 June 2014

combinatorics - Prove the following by two different methods, one combinatorial and one algebraic



Reading through my textbook I came across the following problem, and I am looking for some help solving it. I am asked to prove the following by two different methods, one combinatorial and one algebraic. If I could get help with either or both it would be great, thanks!



Prove that this identity is true,



$$\binom{n}{k} -\binom{n-3}{k} =\binom{n-1}{k-1} + \binom{n-2}{k-1} + \binom{n-3}{k-1}$$


Answer



Repeatedly, use the identity (Pascal's Identity), namely

$$
\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}.
$$
Note that
$$
\left(\binom{n}{k}-\binom{n-1}{k-1}\right)-\binom{n-2}{k-1}-\binom{n-3}{k-1}-\binom{n-3}{k}
$$
equals
$$
\binom{n-1}{k}-\binom{n-2}{k-1}-\binom{n-3}{k-1}-\binom{n-3}{k}

$$
which equals
$$
\binom{n-2}{k}-\binom{n-3}{k-1}-\binom{n-3}{k}
$$
which equals
$$
\binom{n-3}{k}-\binom{n-3}{k}=0
$$
as desired.



No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...