Q. 1.11 - A First Course in Probability

Question

The following identity is known as Fermat’s combinatorial identity:

$\left(\begin{array}{c}n\\ k\end{array}\right)=\sum _{i=k}^n\left(\begin{array}{c}i-1\\ k-1\end{array}\right) n\ge k$

Give a combinatorial argument (no computations are needed) to establish this identity.

Hint: Consider the set of numbers $1$ through $n$. How many subsets of size $k$ have $i$ as their highest numbered member?

Step-by-Step Solution

Answer

The possible number of subsets are ${}^{k-1}C_{k-1}+{}^{k}C_{k-1}+{}^{k+1}C_{k-1}+.....+{}^{n-1}C_{k-1}$.

Step 1. Given information.

The given Fermat’s combinatorial identity is $\left(\begin{array}{c}n\\ k\end{array}\right)=\sum _{i=k}^n\left(\begin{array}{c}i-1\\ k-1\end{array}\right) n\ge k$.

Combinatorial Proof considers the numbers $1$ through $n$,

Therefore, $k$ numbers out of $n$ can be selected in ${}^n{C}_k$ ways.

Step 2. Find the number of subsets.

The number of sets having a maximum number as $k-1$ or less is $= 0$

(As $k$ numbers have to be there in set)

The number of sets having a maximum number as $k$ is equivalent to selecting $(k-1)$ numbers out of $(k-1)$ left members. This can be done in ${}^{k-1}C_{k-1}$ ways.

The number of sets having a maximum number as $k+1$ is ${}^{k}C_{k-1}$ (selecting the other k-1 numbers from k numbers left).

Similarly, $n$ number of sets having number $n$ as the maximum one is ${}^{n-1}C_{k-1}$.

Adding $\left(1\right) \text{to} \left(n\right)$, we get all the possible ways of selecting the k numbers that is $={}^{k-1}C_{k-1}+{}^{k}C_{k-1}+{}^{k+1}C_{k-1}+.....+{}^{n-1}C_{k-1}$

Hence, it is proved that $\left(\begin{array}{c}n\\ k\end{array}\right)=\sum _{i=k}^n\left(\begin{array}{c}i-1\\ k-1\end{array}\right) n\ge k$.