How can you prove the N choose k formula without using a formula?

[mattmns]

Hello.

I have the following problem: Show that for m,n \geq2,

\left(\begin{array}{cc}m+n\\2\end{array}\right) = \left(\begin{array}{cc}m\\2\end{array}\right) + \left(\begin{array}{cc}n\\2\end{array}\right) + mn

by using the formula

\left(\begin{array}{cc}a\\b\end{array}\right) = \frac{a!}{(a - b)!b!}

and algebra. Prove it again without using this formula.

The first part was quite easy, but I am not sure how I could solve the second (bold) part without using a formula. Am I supposed to use a definition or something of that nature? I just am not seeing it, any ideas would be appreciated. Thanks

 

[Tide]

You could use Pascal's triangle and note that the third item in row N is the sum of the items in the third diagonal with values 1+2+ \cdot\cdot\cdot \+ N-1 which is just an arithmetic series.

 

[Muzza]

Take two disjoint sets, one having m elements and the other having n elements, and count the number of 2-subsets of their union in two different ways.