Question

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 subset of the integers${\mathbf{2}}^{\mathbf{0}}\mathbf{=}\mathbf{1}\mathbf{,}{\mathbf{2}}^{\mathbf{1}}\mathbf{=}\mathbf{2}\mathbf{,}{\mathbf{2}}^{\mathbf{2}}\mathbf{=}\mathbf{4}\mathbf{,}$ and so on. [Hint: For the inductive step, separately consider the case where$\mathit{k}\mathbf{+}\mathbf{1}$ is even and where it is odd. When it is even, note that$\left(k+1\right)\mathbf{/}\mathbf{2}$ is an integer.]

Short answer

It has been proved that every positive integer n can be written as a sum of distinct powers of two, that is, as a sum of subset of the integers$2^0=1,2^1=2,2^2=4,$ and so on.

Step-by-step solution

Describe given information

Given a positive integer n. It is to be shown that as a sum of distinct powers of two, that is, as a sum of subset of the integers

Using strong induction

The basis step: Note that $1=2^0,2=2^1,3=2^1+2^0,4=2^2,2^2+2^0$, , , , and so on.

This is the representation of a number in binary form.

Inductive hypothesis: Every positive integer up to k can be written as a sum of distinct powers of 2.

To show: The statement$P(k+1)$ is true.

Proof:There arise two cases:

If $k+1$ is odd, then k is even, so $2^0$was not part of the sum k. Therefore the sum for $k+1$is same as the sumk for with the extra term added.