2
$\begingroup$

Need help trying to prove this problem algebraically. $$\binom{n+m}{2} = nm + \binom{n}{2} + \binom{m}{2}$$

The farthest I've got is simplifying the RHS to $$nm + \frac{n(n-1)}{2!} + \frac{m(m-1)}{2!}$$ but not sure what to do after that.

$\endgroup$
9
  • $\begingroup$ just modify n(n-1)/2! to n!/[(n-2)!2!]=nC2 $\endgroup$
    – TYZ
    Commented Mar 13, 2014 at 20:22
  • $\begingroup$ What is RHS.....? $\endgroup$
    – RSh
    Commented Mar 13, 2014 at 20:22
  • $\begingroup$ What is your notation exactly? Do the brackets present binomial coefficients? $\endgroup$
    – Marc
    Commented Mar 13, 2014 at 20:22
  • $\begingroup$ You've all but solved your problem entirely. What are the formulas for ${n \choose 2}$ and ${m \choose 2}$ as ratios of factorials? $\endgroup$ Commented Mar 13, 2014 at 20:26
  • 2
    $\begingroup$ Perhaps try replacing the $\binom x 2$ notation with something more familiar, using the definition of that notation. $\endgroup$
    – MJD
    Commented Oct 21, 2014 at 18:37

8 Answers 8

4
$\begingroup$

I like bijective proofs :)

Let's say $A$ is a set of $n$ elements and $B$ is a set of $m$ elements.

We have 2 ways to count the number of $2$ element subsets of $A\cup B$.

  • $\binom{m+n}2$ if we count them together.
  • $\binom n2+\binom m2+nm$ by first counting subsets of $A$, then subsets of $B$ and finally subsets where one element is from $A$ and the other from $B$.
$\endgroup$
4
$\begingroup$

By definition,

$$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$

Hence,

\begin{align*} nm + \binom{n}{2} + \binom{m}{2} & = nm + \frac{n!}{2!(n - 2)!} + \frac{m!}{2!(m - 2)!}\\ & = nm + \frac{n(n - 1)(n - 2)!}{2 \cdot 1 \cdot (n - 2)!} + \frac{m(m - 1)(m - 2)!}{2 \cdot 1 \cdot (m - 2)!}\\ & = nm + \frac{n(n - 1)}{2} + \frac{m(m - 1)}{2}\\ & = \frac{2nm + n(n - 1) + m(m - 1)}{2}\\ & = \frac{2nm + n^2 - n + m^2 - m}{2}\\ & = \frac{n^2 + 2nm + m^2 - n - m}{2}\\ & = \frac{(n + m)^2 - (n + m)}{2}\\ & = \frac{(n + m)(n + m - 1)}{2}\\ & = \frac{(n + m)(n + m - 1)(n + m - 2)!}{2(n + m - 2)!}\\ & = \frac{(n + m)!}{2!(n + m - 2)!}\\ & = \binom{n + m}{2} \end{align*}

$\endgroup$
2
$\begingroup$

You just need to expand those binomial coefficients.

you get the equivalent

$$\frac{(n+m)(n+m-1)}{2} = nm + \frac{n(n-1)}{2} + \frac{m(m-1)}{2}$$

Now you just need to simplify it and you'll find out it is indeed an identity ;-)

$\endgroup$
2
$\begingroup$

$${n+m\choose2}=mn+{n\choose2}+{m\choose2}$$ Without loss of generality we will prove this identity by induction on $m$. Notice that for $m=2$ \begin{align}{n+2\choose2}&=\frac{(n+2)!}{n!2!}=\frac{(n+2)(n+1)n!}{n(n-1)(n-2)!2!}=\frac{(n+2)(n+1)}{n(n-1)}\cdot{n\choose2}\\&=\frac{n(n-1)+4n+2}{n(n-1)}\cdot{n\choose2}={n\choose2}+\frac{4n+2}{n(n-1)}\cdot{n\choose2}={n\choose2}+\frac{4n+2}{2}\\&={n\choose2}+1+2n={n\choose2}+{2\choose2}+2n\end{align} for $m=3$ \begin{align}{n+3\choose2}&=\frac{n+3}{n+1}{n+2\choose2}=\frac{n+3}{n+1}({n\choose2}+{2\choose2}+2n)=(1+\frac{2}{n+1})({n\choose2}+{2\choose2}+2n)\\&={n\choose2}+{2\choose2}+2n+\frac{n(n-1)}{n+1}+\frac{2}{n+1}+\frac{4n}{n+1}\\&={n\choose2}+{2\choose2}+2n+\frac{(n+1)(n+2)}{n+1}={n\choose2}+{2\choose2}+3n+2\\&={n\choose2}+{3\choose2}+3n \end{align} Assume identity holds true for $m=k$. Let $m=k+1$ then \begin{align}{n+k+1\choose2}&=\frac{(n+k+1)!}{(n+k-1)!2!}=\frac{(n+k+1)(n+k)!}{(n+k-1)(n+k-2)!2!}\\&=\frac{n+k+1}{n+k-1}{n+k\choose2}\\&=\frac{n+k+1}{n+k-1}(nk+{n\choose2}+{k\choose2})\\&=(1+\frac{2}{n+k-1})(nk+{n\choose2}+{k\choose2})\\&=nk+{n\choose2}+{k\choose2}+\frac{2nk}{n+k-1}+\frac{n(n-1)}{n+k-1}+\frac{k(k-1)}{n+k-1}\\ &=nk+{n\choose2}+{k\choose2}+\frac{(n+k)(n+k-1)}{n+k-1}\\ &=nk+{n\choose2}+{k\choose2}+(n+k)\\ &=n(k+1)+{n\choose2}+{k\choose2}+k\\ &=n(k+1)+{n\choose2}+\frac{k!}{(k-2)!2!}+k\\ &=n(k+1)+{n\choose2}+\frac{k!+2k(k-2)!}{(k-2)!2!}\\ &=n(k+1)+{n\choose2}+\frac{(k+1)k(k-2)!}{(k-2)!2!}\\ &=n(k+1)+{n\choose2}+\frac{(k+1)!}{(k-1)!2!}\\ &=n(k+1)+{n\choose2}+{k+1\choose2} \end{align}

$\endgroup$
0
2
$\begingroup$

Look at the LHS- it is simply choosing 2 elements from a $(m+n)$ element set. Split this set into set $A$, containing $m$ elements, and set $B$, containing $n$ elements.

Now, when we choose 2 elements from the original set, we may do so either by choosing 1 from $A$ and $B$ each, or 2 from each. Therefore, the required identity is achieved:

$\binom{n+m}{2}=\binom{m}{2} +\binom{n}{2} +mn$, since $\binom{m}{1}=m, \binom{n}{1}=n$

$\endgroup$
2
  • $\begingroup$ always nice to see the combinatoric solution. $\endgroup$ Commented Oct 21, 2014 at 23:42
  • $\begingroup$ @MitchWheat Thanks ^__^ $\endgroup$ Commented Oct 22, 2014 at 3:48
2
$\begingroup$

Hint for an algebraic proof: Consider the identity $(1 + x)^{m+n} = (1 + x)^m (1 + x)^n$ and expand using the binomial theorem. Your identity will pop out by matching up the coefficients of an appropriate power of $x$, which I leave for you to figure out.

$\endgroup$
1
$\begingroup$

Hint: The LHS is equal to $\frac{(n+m)(n+m-1)}{2}$. Get the RHS under one fraction and show that the two are equal.

$\endgroup$
0
$\begingroup$

Consider a group of persons with $m$ of them men, $n$ of them women. How many ways can you pick a team of 2 persons from those $n+m$ persons? It is $n+m\choose 2$.

Other way of counting the same thing is: categorize the teams into 3 kinds: (i) Men-only teams (ii) women-only teams and (iii) team with one man and one woman.

Men-only team are $m\choose 2$ in number, women-only team are $n\choose 2$ in number; a mixed team means one man from $m$ and one woman from $n$ which makes it $mn$ choices. This total should be the same as the previous calculation.

$\endgroup$
2
  • $\begingroup$ You're a little late... $\endgroup$
    – Theorem
    Commented Oct 8, 2016 at 11:05
  • $\begingroup$ @Theoniix: After your comment I noticed that this question was asked in March 2014. I don't how I ended up seeing this question $\endgroup$ Commented Oct 8, 2016 at 11:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .