Home > Precalculus > Sums of Arithmetic Sequences

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#}?

Answer 1

Chloe Alexander

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

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#

By signing up, you agree to our Terms of Service and Privacy Policy

Answer 2

Chloe Alexander

For the set {1, 2, 4, 8}, the number of different sums that can be obtained by using one, some, or all of the numbers is 15.

For the set {2^0, 2^1, 2^2, ..., 2^n}, where n is a non-negative integer, the number of different sums that can be obtained by using one, some, or all of the numbers is (2^{n+1} - 1).

By signing up, you agree to our Terms of Service and Privacy Policy

Answer from HIX Tutor

When evaluating a one-sided limit, you need to be careful when a quantity is approaching zero since its sign is different depending on which way it is approaching zero from. Let us look at some examples.