ONE MORE STEP TOWARD BETTER TOMORROW : CHAPTER 5

Tuesday, 5 August 2014

CHAPTER 5 - Worked Out Examples

Example: 1

Prove that $^n{C_0} + {\,^n}{C_1} + {\,^n}{C_2} + \ldots + {\,^n}{C_n} = {2^n}$

Solution: 1

This looks like a tough one! Lets first interpret what the left side means. $^n{C_0}$ is the number of ways in which we can select ‘nothing’ out of $n$ things (there will obviously be only one such way: that we do nothing!). $^n{C_1}$ is the number of ways in which we can select $1$ thing out of $n$ . $^n{C_r}$ is the number of ways of selecting $r$ things out of $n$ . We want the value of the sum $\mathop {\mathop \sum \limits_{r = 0} }\limits^n {\,^n}{C_r}$ , which is the number of all groups possible of any size what so ever. Thus, our selection could be any size from $0$ to $n$ (both inclusive); what we want is the total number of selections possible.

For example, consider the set $\{A, B, C\}$ . The set of all possible selections that can be made from this set is $\left\{ {\phi ,\left\{ A \right\},\left\{ B \right\},\left\{ C \right\},\left\{ {AB} \right\},\left\{ {AC} \right\},\left\{ {BC} \right\},\left\{ {ABC} \right\}} \right\}.$ Thus, $8$ total different selections are possible (note that ) $8 = {2^3}$

To count the total number of selections possible if we have $n$ persons, we adopt an individual’s perspective. An individual can either be or not be in our selection. Thus, we have two choices with respect to any individual; we either put him in our group or do not put him in our group.

These two choices apply to every individual. Also, choosing or not choosing any individual is independent of choosing or not choosing another. Thus, the total number of ways in which an arbitrary number of individuals can be selected from $n$ people is $\underbrace {2 \times 2 \times 2 \times \ldots \times 2}_{n\,\,{\rm{times}}} = {2^n}$

This proves that

$\sum\limits_{i = 0}^n {^n{C_i} = {2^n}}$

Example: 2

Prove that $^{n + m}{C_r} = {\,^n}{C_0}{\,^m}{C_r} + {\,^n}{C_1}{\,^m}{C_{r - 1}} + {\,^n}{C_2}^n{C_{r - 2}} + \ldots + {\,^n}{C_r}^m{C_0}$

Solution: 2

We interpret the left hand side as the number of ways of select $r$ people out of a group of $(n + m)$ people.

Let this group of $(n + m)$ people consist of $n$ boys and $m$ girls. A group of $r$ people can be made in the following ways:

SI.	Group contains	No. of ways possible
$1$	$0$ boys, $r$ girls	${}^n{C_0} \times {}^m{C_r}$
$2$	$1$ boy, $(r - 1)$ girls	${}^n{C_1} \times {}^m{C_{r - 1}}$
$3$	$2$ boys, $(r - 2)$ girls	${}^n{C_2} \times {}^m{C_{r - 2}}$
$.$
$.$
$.$
$r$	$(r - 1)$ boys, $1$ girl	${}^n{C_{r - 1}} \times {}^m{C_1}$
$(r+1)$	$r$ boys, $0$ girls	${}^n{C_r} \times {}^m{C_0}$