Use strong induction to show that every positive integer n c

Use strong induction to show that every positive integer n

can be written as a sum of distinct powers of two, that is,

as a sum of a subset of the integers 20 =1, 21 =2, 22 =4,

and so on. [Hint: For the inductive step, separately consider

the case where k + 1 is even and where it is odd.

When it is even, note that (k + 1)/2 is an integer.]

Solution

Given: sum of a subset of the integers 20 =1, 21 =2, 22 =4,and so on

For the inductive step, separately consider the case where k + 1 is even and where it is odd. When it is even, note that (k + 1)/2 is an integer

Let P(n) be the claim that n can be written as a sum of distinct powers of two.

We show that P(n) is true for all positive integers n.

let\'s

As 1 = 20 , we have that P(1) is true.

Lets Assume for a positive integer k that P(i) is true for all 1 i k.

We consider two cases, namely when k + 1 is even and when k + 1 is odd.

If k + 1 is even, then (k + 1)/2 is an integer, and by the inductive hypothesis,

we can express (k + 1)/2 by a sum of distinct powers of two.

We can then multiply this sum by 2, which simply increases the exponent of each power of two by 1, so this is again a sum of distinct powers of two that is equal to k + 1.

When k+1 is odd, we have that k is even.

By the inductive hypothesis, we can express k as a sum of distinct powers of two.

However, since k is even, the sum cannot contain 2 0 = 1.

Thus, we can add 20 to this sum, which remains a sum of distinct powers of two, and equals k + 1.

Thus, in both cases, we can express k + 1 as a sum of distinct powers of two

so when P(i) is true for all 1 i k,

we have that P(k + 1) is true.

Since P(1) is true, this means that the claim is true for all positive integers, as show by strong induction.