Q. 1.14 - A First Course in Probability

Question

From a set of $n$ people, a committee of size $j$ is to be chosen, and from this committee, a subcommittee of size $i$, $i\le j$, is also to be chosen.

(a) Derive a combinatorial identity by computing, in two ways, the number of possible choices of the committee and subcommittee—first by supposing that the committee is chosen first and then the subcommittee is chosen, and second

by supposing that the subcommittee is chosen first and then the remaining members of the committee are chosen.

(b) Use part (a) to prove the following combinatorial identity:  $\sum _{j=i}^n\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)=\left(\begin{array}{c}n\\ i\end{array}\right)2^{n-i}; i\le n$

(c) Use part (a) and Theoretical Exercise 13 to show that:  $\sum _{j=i}^n\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right){\left(-1\right)}^{n-j}=0; i<n$

Step-by-Step Solution

Answer

(a) The combinatorial identity is $\left(\begin{array}{c}n-i\\ j-i\end{array}\right)=\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)$.

(b) It is proved that $\sum _{j=i}^n\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)=\left(\begin{array}{c}n\\ i\end{array}\right)2^{n-i}$

(c) It is proved that $\sum _{j=i}^n\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right){\left(-1\right)}^{n-j}=0$

Part (a) Step 1. Given information.

A committee of size $j$ is to be chosen from a set of $n$ people. From this committee, a sub-committee of size $i$ has to be selected.

So, $i\le j$.

Part (a) Step 2. Derive a combinatorial identity.

The two conditions are - 

1) Committee is chosen first then the sub-committee

2) Sub-committee is chosen first then the remaining members of committee

For case 1, where the committee is chosen first then the sub-committee, 

No. of ways of selecting a committee of $j$ members from $n$ persons will be $\left(\begin{array}{c}n\\ j\end{array}\right)$.

No. of ways of selecting a sub-committee of $i$ members from $j$ members will be $\left(\begin{array}{c}j\\ i\end{array}\right)$.

Therefore, the no. of possible ways of selecting $i$ members of the subcommittee and $j$ members of the committee is $\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)$.

For case 2, where the sub-committee is chosen first then the remaining members of committee, 

No. of ways of selecting a sub-committee of $i$ members from $n$ members will be $\left(\begin{array}{c}n\\ i\end{array}\right)$.

No. of ways of selecting remaining $j-i$ members committee from $n-i$ persons will be  $\left(\begin{array}{c}n-i\\ j-i\end{array}\right)$

Therefore, $\left(\begin{array}{c}n-i\\ j-i\end{array}\right)=\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)$

Part (b) Step 1. Prove that &#8721; j = i n n j j i = n i 2 n - i

For Case 1 - The no. of ways of selecting  members of the subcommittee and  members of the committee is $\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)$.

The size of committee can vary from $1 \text{to} n$, and the size of subcommittee can vary from $j \text{to} n$ so total possibilities is $\sum _{j=i}^n\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)$.

For Case 2 - The no. of ways of selecting  members of the subcommittee is $\left(\begin{array}{c}n\\ i\end{array}\right)$.

The remaining $(j-1)$ committee members will selected from $(n-i)$ committee members. Each of the $(n-i)$ members have two chances - they can be included or they can not be included in the committee.

So, the different possible selections of $(n-i)$ committee members is $2^{n-i}$. 

Therefore, the possible selections of committee and sub-committee members is $\sum _{j=i}^n\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)=\left(\begin{array}{c}n\\ i\end{array}\right)2^{n-i}$.

Part (c) Step 1. Prove that &#8721; j = i n n j j i - 1 n - j = 0

We have to prove that $\sum _{j=i}^n\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right){\left(-1\right)}^{n-j}=0$ for $i\le n$

Taking the L.H.S of the equation, we have

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

From part (a) the different possible combinations of selecting a committee and a sub-committee is $\left(\begin{array}{c}n-i\\ j-i\end{array}\right)=\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)$ ...... (1)

From equation 1, we get

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

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

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

Let $n-i=k$

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

For $n>0$

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

From equation (2) and (3), it is proved that

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