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,



(nk)(n3k)=(n1k1)+(n2k1)+(n3k1)


Answer



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

(nk)=(n1k)+(n1k1).


Note that
((nk)(n1k1))(n2k1)(n3k1)(n3k)

equals
(n1k)(n2k1)(n3k1)(n3k)

which equals
(n2k)(n3k1)(n3k)

which equals
(n3k)(n3k)=0

as desired.



No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

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