Adding combinations

Question

Show non-numerically that:

$${2\choose2} + {3\choose2} + {4\choose2} + {5\choose2} = {6\choose3}$$

The answer is as follows, but I have no idea how it was done:

$$ \begin{eqnarray} &\phantom{=}& {2\choose2} + {3\choose2} + {4\choose2} + {5\choose2} \\ &=& {3\choose3} + {3\choose2} + {4\choose2} + {5\choose2} \\ &=& {4\choose3} + {4\choose2} + {5\choose2} \\ &=& {5\choose3} + {5\choose2} \\ &=& {6\choose3} \end{eqnarray} $$

Could anyone please explain this? Thank you!

Look at http://en.wikipedia.org/wiki/Pascal%27s_triangle – JB King Jun 03 '14 at 03:54 — JB King, Jun 03 '14 at 03:54
This is a case of the hockey-stick identity. – user2357112 Jun 03 '14 at 07:46 — user2357112, Jun 03 '14 at 07:46

score 5 · Answer 1 · answered Jun 03 '14 at 04:06

If you want to choose $k$ items from $n$ items, you can do either way:

choose $k$ items from the first $n-1$ items.
choose the last item, and then choose $k-1$ items from the first $n-1$ items.

That means

${n\choose k} = {n-1\choose k} + {n-1\choose k-1}$

score 3 · Accepted Answer · answered Jun 03 '14 at 04:02

One way to think about it is that in order to pick 3 out 6 one thing you can do is to pick the 6th one and then pick 2 out of the first 5... or you can skip the sixth one, pick the fifth one and then 2 out of the first 4, or you can skip 5 and 6 but pick the fourth one and 2 out of the first 3, or skip numbers 4, 5 and, but then you must pick the third plus 2 out of the first 2 (since you have to have 3 of the original 6). That means C(6,3) = C(5,2) + C(4,2) + C(3,2) + C(2.2).

Adding combinations

2 Answers2