Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$8.$ ($6$ points) Verify that for any $n\ge k\ge 1$ $$\binom{n}2=\binom{k}2+k(n-k)+\binom{n-k}2\;.$$ $\quad$Then give a combinatorial argument for why this is true.

Hi I need help doing this problem

I know this is a given $\binom{n}{2} = \binom{k}{2} + k \cdot (k-1) \binom{n-l}{2}$

Also what is a combinatorial argument as well

share|improve this question

1 Answer 1

HINT: Let $X$ be a set of $n$ objects; $\binom{n}2$ is the number of $2$-element subsets of $X$. Now split $X$ into two disjoint subsets $Y$ and $Z$ in such a way that $Y$ contains $k$ objects, and $Z$ contains the other $n-k$ objects. Split the $2$-element subsets of $X$ into those whose elements are both in $Y$, those with one element from $Y$ and one from $Z$, and those whose elements are both from $Z$. How big is each of those three sets of pairs?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.