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 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.]

Answer 1

Answer:

Step-by-step explanation:

The Strong Induction Principle establishes that if a a subset S of the positive integers satisfies:

• S is a non-empty set.
• If m+1, m+2, ..., m+k ∈ S then m+k+1 ∈ S.

Then, we have that n ∈ S for all n ≥ k.

1. Base case: Now, in our problem let S be the set of positive numbers than can be written as a sum of distinct powers of 2. Note that S is non-empty because, for example, 1, 2, 3 and 4 belongs to S: $1=2^0, 2=2^1, 3=2^0+2^1, 4=2^2.$ This is the so called base case, and in the definition above we set k = 1.
2. Inductive step: Now suppose that 1, 2, 3, .., k ∈ S. This is the inductive hypothesis. We are going to show that k+1 ∈ S. By hypothesis, since k ∈ S, it can be written as a sum of distinct powers of two, namely, $k=a_02^0+a_12^1+a_22^2+\cdots+a_t2^t,$ where $a_i\in\{0,1\}$, i.e., every power of 2 occurs only once or not appear. Using the hint, we consider two cases:

• k+1 is odd: In this case, k must be even. Note that $a_0=1$. If not were the case, then $a_0=0$ and we can factor 2 in the representation of k: $k=2(a_12+a_22^1+\cdot+a_t2^{t-1}$ This will lead us to the contradiction that k is even. Then, adding 1 to k we obtain:$k+1=1+(a_12^1+a_22^2+\cdot+a_t2^t)=k=2^0+a_12^1+a_22^2+\cdot+a_t2^t.$
• k+1 is even: Then $\dfrac{k+1}{2}$ is an integer and is smaller than k, which means by the inductive hypothesis that belongs to S, that is, $\dfrac{k+1}{2}=b_02^0+b_12^1+b_22^2+\cdots+b_r2^r,$ where $b_i\in\{0,1\}$, for all $i=0,1,2,\ldots,r$. Therefore, multiplying both sides by 2, we obtain $k+1=2(b_02^0+b_12^1+b_22^2+\cdots+b_r2^r)=b_02^1+b_12^2+b_22^3+\cdots+b_r2^{r+1}.$ This is a sum of distinct powers of 2, which implies that k+1 ∈ S.

Then we can conclude that n ∈ S , for all n ≥ 1, that is, every positive integer n can be written as a sum of distinct powers of 2.