Question

The number 3 can be expressed as a sum of one or more positive integers, taking order into account, in four ways, namely: 3, 1 + 2, 2 + 1, and 1 + 1 + 1. Show that any positive-integer n can be so expressed in r-1 ways.

Answer 1

Explanation:

We can see this exercise as any integer can be expressed as
`2^(n-1)`, explained this way:

n=1+1+1+...+1 (n times. )

But there is a problem, this only makes so any number is a sum of ones, we want all combinations of sums. We have another resource to look into, the number of "+" signs. For each + we have an option to associate the surrounding numbers. For example, 4:

4=1+1+1+1

This one, associating by the +'s can be:

4=(1+1)+1+1 4=(1+1+1)+1 4=1+(1+1)+1 etc.

If we add up the sums in between the parenthesis, we have:

4=2+1+1 4=3+1 4=1+2+1

Some expressions of 4 as a sum of positive integers.

Now if we look at this from the number of + signs, then there are n−1 plus signs between the number of 1s, or
`2^(n-1)` ways of choosing where to split the sum, or
`2^(n-1)` possible sums.