91Ó°ÊÓ

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

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 localid="1648192158194" $\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 localid="1648199117263" $\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 localid="1648192233272" $n-i$persons will be $\left(\begin{array}{c}n-i\\ j-i\end{array}\right)$

Therefore,localid="1648199717056" $\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)$

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$\underset{j=i}{\overset{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 role="math" localid="1648199397334" $\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$\underset{j=i}{\overset{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}$.

We have to prove that $\underset{j=i}{\overset{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≤n$

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

role="math" localid="1648199810708" $\underset{j=i}{\overset{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

role="math" localid="1648200521201" $\underset{j=i}{\overset{n}{∑}}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right){\left(-1\right)}^{n-j}=\underset{j=i}{\overset{n}{∑}}\left(\begin{array}{c}n-i\\ j-i\end{array}\right){\left(-1\right)}^{n-j}$

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

$\underset{j=i}{\overset{n}{∑}}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right){\left(-1\right)}^{n-j}=\underset{j-1=0}{\overset{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$

role="math" localid="1648200825487" $\underset{j=i}{\overset{n}{∑}}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right){\left(-1\right)}^{n-j}=\underset{k=0}{\overset{n-i}{∑}}\left(\begin{array}{c}n-i\\ k\end{array}\right){\left(-1\right)}^{n-i-k}$.................... (2)

For $n>0$

$\underset{i=0}{\overset{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

$\underset{j=i}{\overset{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$