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.

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$.

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*}

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 ;-)

$${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}