Problem 9:

Given a natural number *n*,
list all the ways that it can written as a sum of smaller (or equal) natural
numbers. Such a sum is called a partition of *n. *And since order of
summation is irrelevant, we may assume that the summands are written in
increasing order. For example for *n=5, *we get the following list of all
7 partitions:

5=1+1+1+1+1 =

5=1+1+1+2 =

5=1+1+3 =

5=1+2+2 =

5=1+4 =

5=2+3 =

5=5 =

The right column gives a way
of abbreviating partitions. Using this abbreviation, I can finally state the
equation that you are to prove for this problem. Here it is: prove that for
any *n,*

Sticking with our earlier
example, what this says for *n=5 *is: