perplexus.info :: Numbers : Power partition procedure

Power partition procedure (Posted on 2017-03-26)

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 2^{n - 1}ways.

See The Solution Submitted by Ady TZIDON

No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)

Another solution

| Comment 2 of 5 |

The number doubles when n is increased by 1. This is because there are two ways to make a sum of n become a sum of n+1:

(A) Add 1 at the end

(B) Add 1 to the last number

Using the given sums to 4, applying (1) to each gives the first 8

4+1; 3+1+1; 1+3+1; 2+2+1; 2+1+1+1; 1+2+1+1; 1+1+2+1; 1+1+1+1+1

Applying rule 2 to each gives 8 more

5; 3+2; 1+4; 2+3; 2+1+2; 1+2+2; 1+1+3; 1+1+1+2

The rules can't cause any repeats because with rule (A) they all end in 1 and with rule (B) they can't end in 1.

To finish this recursive rule, note that 1 can be done in 2⁰=1 way: 1

Posted by Jer on 2017-03-26 14:33:59

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (16)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info