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

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
  `(k+1)/(2)` is an integer and is smaller than k, which means by the inductive hypothesis that belongs to S, that is,
  `(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.