How to algebraically prove $\binom{n+m}{2} = nm + \binom{n}{2} + \binom{m}{2}$? 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.
 A: 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$.

A: 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*}
A: 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 ;-)
A: 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$
A: $${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}
A: 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.
A: 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.
A: 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.
