Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: N choose k like problem

  1. Nov 8, 2005 #1

    I have the following problem: Show that for [tex]m,n \geq2[/tex],

    [tex]\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[/tex]

    by using the formula

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

    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
    Last edited: Nov 8, 2005
  2. jcsd
  3. Nov 9, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    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 [itex]1+2+ \cdot\cdot\cdot \+ N-1[/itex] which is just an arithmetic series.
  4. Nov 9, 2005 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook