Question

Give an analytic verification of

$\left(\begin{array}{c}n\\ 2\end{array}\right)=\left(\begin{array}{c}k\\ 2\end{array}\right)+k(n-k)+\left(\begin{array}{c}n-k\\ 2\end{array}\right),1\le k\le n$

Now, give a combinatorial argument for this identity.

Short answer

It is proved that$\left(\begin{array}{c}n\\ 2\end{array}\right)=\left(\begin{array}{c}k\\ 2\end{array}\right)+k(n-k)+\left(\begin{array}{c}n-k\\ 2\end{array}\right)$

Step-by-step solution

Step 1. Given information.

We have to verify that

$\left(\begin{array}{c}n\\ 2\end{array}\right)=\left(\begin{array}{c}k\\ 2\end{array}\right)+k(n-k)+\left(\begin{array}{c}n-k\\ 2\end{array}\right)$

where

$1\le k\le n$

Step 2. Verify the given equation.

The given equation is $\left(\begin{array}{c}n\\ 2\end{array}\right)=\left(\begin{array}{c}k\\ 2\end{array}\right)+k(n-k)+\left(\begin{array}{c}n-k\\ 2\end{array}\right)$.

On expanding the L.H.S we get,

$$\begin{gathered} \left(\begin{array}{c}n\\ 2\end{array}\right)=\frac{n}{2}\times \frac{n-1}{2-1}\times \left(\begin{array}{c}n-2\\ 2-2\end{array}\right) \\ \Rightarrow \left(\begin{array}{c}n\\ 2\end{array}\right)=\frac{n\left(n-1\right)}{2} \\ \therefore L.H.S=\frac{n\left(n-1\right)}{2} \end{gathered}$$

On expanding R.H.S we get,

$\left(\begin{array}{c}k\\ 2\end{array}\right)+k(n-k)+\left(\begin{array}{c}n-k\\ 2\end{array}\right)=\frac{k}{2}\times \frac{k-1}{2-1}\times \left(\begin{array}{c}k-2\\ 2-2\end{array}\right)+k(n-k)+\frac{n-k}{2}\times \frac{n-k-1}{2-1}\times \left(\begin{array}{c}n-k-2\\ 2-2\end{array}\right)$

$$\begin{gathered} =\frac{k\left(k-1\right)}{2}+k(n-k)+\frac{n-k\left(n-k-1\right)}{2} \\ =\frac{k\left(k-1\right)}{2}+\frac{2k(n-k)}{2}+\frac{n-k\left(n-k-1\right)}{2} \\ =\frac{k^2-k+2kn-2k^2+n^2-kn-n-kn+k^2+k}{2} \\ =\frac{n^2-n}{2} \\ =\frac{n\left(n-1\right)}{2} \end{gathered}$$

$\therefore R.H.S=\frac{n\left(n-1\right)}{2}$

Therefore, L.H.S = R.H.S

Hence, it is proved thatlocalid="1649216494198" $\left(\begin{array}{c}n\\ 2\end{array}\right)=\left(\begin{array}{c}k\\ 2\end{array}\right)+k(n-k)+\left(\begin{array}{c}n-k\\ 2\end{array}\right)$

Step 3. Give argument.

The given identity $\left(\begin{array}{c}n\\ 2\end{array}\right)=\left(\begin{array}{c}k\\ 2\end{array}\right)+k(n-k)+\left(\begin{array}{c}n-k\\ 2\end{array}\right)$is a combinatorial argument for a group of $n$objects and a subgroup of $k$of the $n$objects.

$\left(\begin{array}{c}k\\ 2\end{array}\right)$is the number of subsets of size $2$that contains $2$objects from the subgroup of size $k$,

$k(n-k)$is the number that contain $1$ item from the subgroup and $\left(\begin{array}{c}n-k\\ 2\end{array}\right)$is the number that contain $0$objects from the subgroup.

$\left(\begin{array}{c}n\\ 2\end{array}\right)$ is the total number of subgroups of size $2$that we get by adding $\left(\begin{array}{c}k\\ 2\end{array}\right),k(n-k),\text{and}\left(\begin{array}{c}n-k\\ 2\end{array}\right)$.

Therefore, it is proved that$\left(\begin{array}{c}n\\ 2\end{array}\right)=\left(\begin{array}{c}k\\ 2\end{array}\right)+k(n-k)+\left(\begin{array}{c}n-k\\ 2\end{array}\right)$.