1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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