Tuesday 3 September 2019

combinatorics - Proof of a Binomial Identity using a combinatorial argument



Question



Prove that if $k$ and $l$ are two positive integer with $k ≥ l$, then $\binom{2k}{2} =\binom{k−l}{2}+ \binom{k+l}{2}+ k^2 − l^2$
using a combinatorial argument.



I tried using Vandermonde's Identity and Pascal's Identity but that's leading me nowhere.
Any lead is very welcome.




Thanks


Answer



You want a combinatorial argument...



Say you have $2k$ items and you want to select $2$ of them. Divide the $2k$ items into two groups, one with $k+\ell$ items and one with $k-\ell$ items.



To select two items out of the overall $2k$, you could select two from the group of $k+\ell$ items; or two from the group of $k-\ell$ items; or you could select one from the group of $k+\ell$ and one from the group of $k-\ell$ items. If you add all three possibilities, you should get $\binom{2k}{2}$.



How many ways to pick two from $k+\ell$? How many ways to pick two from $k-\ell$? How many ways to pick one from $k+\ell$ and one from $k-\ell$?


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}...