Question

Ex. 12 p. 342. 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 2^{0}=1, 2^{1}=2, 2^{2}=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.

Answer 1

Explanation:

In this problem we have:

The statement
`P(n)`: Every positive integer
`n` can be written as a sum of distinct powers of two.

We need to prove two steps:

1.Base Case : Prove that the statement
`P(n)` holds when
`n = 1`.

Induction Hypothesis : Assume that for all positive integers less than or equal to
`n`, the statement holds.

2. Inductive Step : Prove, using the Induction hypothesis, that must
`P(n + 1)` be true.

Proof:

1.Base case: Since
`1=2^0` then the statement
`P(1)` holds.

2.Inductive Step:

Fix a positive integer
`n` and suppose that
`P(k)` holds for all
`k \leq n`.

Case 1:
`n+1` is even, then
`(n+1)/(2)` is an integer and we have that
`{ {{1+1<n+1\leq n+n} }`, then
`1< (n+1)/(2)\leq n`. Since
`(n+1)/(2)\leq n`, by the inductive hypothesis, there exists
`\alpha _1, \alpha _2,... ,\alpha _j` such that
`(n+1)/(2)= 2^(\alpha _1) + 2^(\alpha _2)+ ... + 2^(\alpha _j)` and
`a_r\\eq a_s` for every
`r,s`∈
`\{1,2,...,j\}`. Then

`n+1=2((n+1)/(2))=2( 2^(\alpha _1) + 2^(\alpha _2)+ ... + 2^(\alpha _j))= 2^(\alpha _1+1) + 2^(\alpha _2+1)+ ... + 2^(\alpha _n+1.)`

All elements of the set
`\{\alpha _1 + 1, \alpha _2 + 1, ..., \alpha _j + 1\}` are distinct. Suppose that there exists
`r,s`∈
`\{1,2,...,j\}` such that
`\alpha _r + 1= \alpha _s + 1` , then subtracting 1 from both sides of this equation, we get
`\alpha _r=\alpha _s` , this is a contradiction because we are assuming that all the powers
`\alpha _1, \alpha _2,... ,\alpha _j` are distinct. Therefore the statement holds when
`n+1` is even.

Case 2:
`n+1` is odd.

In this case
`n` is even, by the inductive hypothesis we know that
`n=2^(\alpha _1) + 2^(\alpha _2)+ ... + 2^(\alpha _j)`, then
`n+1=2^(\alpha _1) + 2^(\alpha _2)+ ... + 2^(\alpha _j)+2^(0)`. Since
`\alpha _1, \alpha _2,... ,\alpha _j` are all distinct, we only need to prove that 0 ∉
`\{\alpha_1, \alpha_ 2 , ...,\alpha_ j \}`.

If there exists
`r`∈
`\{1,2,...,j\}` such that
`\alpha _r=0`, then
`n=2^(\alpha _1) + 2^(\alpha _2)+ ... + 2^{\alpha _(r-1)}+2^(0) + 2^{\alpha _(r+1)}+...+2^(\alpha _j)\\=2(2^(\alpha _1-1) + 2^(\alpha _2-1)+ ... + 2^{\alpha _(r-1)-1} + 2^{\alpha _(r+1)-1}+...+2^(\alpha _j-1))+1`

but this is a contradiction because
`n` is even, therefore
`\{\alpha_1, \alpha_ 2 , ...,\alpha_ j,0 \}` are distinct powers and the statement holds when
`n+1` is odd. Therefore, the statement that every positive integer
`n` can be written as a sum of distinct powers of two holds for all positive integer.