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?

Short 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-by-step solution

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