Find the number of different sums that can be obtained by using one,some or all of the numbers in the set{1,2,4,8}.Then, how about from {#2^0,2^1,2^2,..,2^n#}?

1 Answer
George C.
Jul 21, 2018

#15" "# or generally #" "2^(n+1)-1#

Explanation:

We can prove this result by induction...

Let #P(n)# be the proposition that the number of different non-empty sums of #{ 2^k : 0 <= k <= n }# is #2^(n+1)-1#

Base case

The number of distinct non-zero sums available from the set #{ 2^0 }# is exactly #1#, namely #2^0 = 1#.

Thus #P(0)# is true.

Induction step

Suppose #P(n)# for some #n#.

Then there are #2^(n+1)-1# distinct possible sums of the numbers #{ 2^0, 2^1, ... , 2^n }#.

The largest is #sum_(k=0)^N 2^n = 2^(n+1)-1#

So there are #2^(n+1)-1# more distinct sums available by adding #2^(n+1) > 2^(n+1)-1#, plus an additional value #2^(n+1)# by taking #2^(n+1)# on its own.

So the number of distinct sums available from #{ 2^0, 2^1,..., 2^(n+1) }# is:

#(2^(n+1) - 1) + (2^(n+1) - 1) + 1 = 2*2^(n+1)-1 = 2^((n+1)+1)-1#

So #P(n+1)# is true.

Conclusion

Since #P(0)# is true and #P(n) => P(n+1)#, we can conclude that #P(n)# holds for all #n >= 0#.

In particular #P(3)# tells us that the number of distinct sums from #{ 1, 2, 4, 8 } = { 2^0, 2^1, 2^2, 2^3 }# is #2^(3+1)-1 = 15#

Related questions
Impact of this question
640 views around the world
You can reuse this answer
Creative Commons License