Let be a fixed positive integer. How many ways are there to write as a sum of positive integers, with an arbitrary positive integer and ? For example with , there are 4 ways:
Solution: Denote to be the set of tuples of with the above properties. We claim that . We will use induction. It is easy to verify the claim for for respectively.
Assume that for some positive integer , then for a given tuple we can add 1 to one of the elements in the tuple, and still preserve the property that . If , then we simply can add 1 where the integers jump, otherwise and we can just have . This gives rise to tuples which are in . Finally, we have a tuple of 1s to add; this results in .
We are not done here, as we would need to show that there exists no other tuples in that we cannot construct as above. This is easy to see, as we can do the inverse operation of subtracting one (with the exception of the tuple of all 1s).