3:

mart [117]

Answer:

Step-by-step explanation:

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

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

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