Number 3 can be expressed as the sum of one or more positive integers in 4 distinct ways:
3; 2 + 1; 1 + 2; 1 + 1 + 1
Number 4 can be expressed as the sum of one or more positive integers in 8 distinct ways:
4; 3 + 1; 1+3; 2 + 2; 2 + 1 + 1; 1+2+1; 1+1+2; 1+1+1+1
Prove : any positive integer n can be so expressed in 2n - 1 ways.
The problem can be thought of as combinations. Row n of Pascal's Triangle sums to 2^n. The ways of expressing n as a sum correspond to row n-1.
I'll demonstrate with n=5
There's 1 way to use one number 4C4=1
5
There are 4 ways to use two numbers. Each number has to be at least 1, you choose where to put the other 3. 4C3=4
4+1
3+2
2+3
1+4
There are 6 ways to use three numbers. Each number has to be at least 1, you choose where to put the other 2. 4C2=6
3+1+1
2+2+1
2+1+2
1+3+1
1+2+2
1+1+3
There are 4 ways to use four numbers. Each number has to be at least 1, you choose where to put the extra 1. 4C1=4
2+1+1+1
1+2+1+1
1+1+2+1
1+1+1+2
There is 1 ways to use 5 numbers. There is nothing extra to place. 4C0=1
1+1+1+1+1
|
|
Posted by Jer
on 2017-03-26 14:26:21 |
One solution
