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

Step-by-step 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.