A combinatorial counting (B2-2004)
by adityaguharoy, Mar 17, 2017, 6:53 AM
For all natural numbers
show that 
Solution


Solution
We consider two activities
each performed with the following objects :
balls all distinct in sizes.
black boxes (all distinct)
white boxes (all distinct)
Define activity
as follows :
Choose any
balls from the collection of
distinct balls. We call these balls chosen and the remaining
balls unchosen.
Distribute the balls in the boxes in such a way that : Every ball goes to a box.
None of the unchosen balls goes to a black box.
None of the chosen balls goes to a white box.
Let
be the set of all possible outcomes of the activity
.
Let
be the total number of ways to complete the activity
.
Define activity
as follows :
Distribute the balls in such a way that every ball goes to some box.
Let
be the set of all possible outcomes of the activity
.
Let
be the total number of ways to complete the activity
.
Then
and
and
So,
and thus,
and thus

This completes the solution.







Define activity






None of the unchosen balls goes to a black box.
None of the chosen balls goes to a white box.
Let


Let


Define activity

Distribute the balls in such a way that every ball goes to some box.
Let


Let


Then

and

and

So,

and thus,


This completes the solution.