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.
- 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: [tex]1=2^0, 2=2^1, 3=2^0+2^1, 4=2^2.[/tex] 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, [tex]k=a_02^0+a_12^1+a_22^2+\cdots+a_t2^t,[/tex] where [tex]a_i\in\{0,1\}[/tex], 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 [tex] a_0=1[/tex]. If not were the case, then [tex]a_0=0[/tex] and we can factor 2 in the representation of k: [tex]k=2(a_12+a_22^1+\cdot+a_t2^{t-1}[/tex] This will lead us to the contradiction that k is even. Then, adding 1 to k we obtain:[tex]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.[/tex]
- k+1 is even: Then [tex]\dfrac{k+1}{2}[/tex] is an integer and is smaller than k, which means by the inductive hypothesis that belongs to S, that is, [tex]\dfrac{k+1}{2}=b_02^0+b_12^1+b_22^2+\cdots+b_r2^r,[/tex] where [tex]b_i\in\{0,1\}[/tex], for all [tex]i=0,1,2,\ldots,r[/tex]. Therefore, multiplying both sides by 2, we obtain [tex]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}.[/tex] 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.
