This looks like a tough one! Lets first interpret what the left side means. is the number of ways in which we can select ‘nothing’ out of things (there will obviously be only one such way: that we do nothing!). is the number of ways in which we can select thing out of . is the number of ways of selecting things out of . We want the value of the sum , which is the number of all groups possible of any size what so ever. Thus, our selection could be any size from to (both inclusive); what we want is the total number of selections possible.
For example, consider the set . The set of all possible selections that can be made from this set is Thus, total different selections are possible (note that )
To count the total number of selections possible if we have 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 people is
This proves that
We interpret the left hand side as the number of ways of select people out of a group of people.
Let this group of people consist of boys and girls. A group of people can be made in the following ways:
No. of ways possible
This table is self-explanatory. The types of groups that have been listed are mutually exclusive. Thus, the total number of -groups is