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!
$\endgroup$ 22 Answers
$\begingroup$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}$
$\endgroup$ $\begingroup$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).
$\endgroup$
