Q. 1.17 - A First Course in Probability

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.

Step-by-Step Solution

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