Use strong induction to show that every positive integer n can be written as a s
ID: 3878029 • Letter: U
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 2^0=1, 2^1=2, 2^2=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.]
a) What is the statement P(1)?
b) Show that P(1) is true, completing the basis step of the proof.
c) What is the inductive hypothesis?
d) What do you need to prove the inductive step?
e) Complete the inductive step, identifying where you use the inductive hypothesis.
f) Explain why these steps show that this formula is true whenever n is a positive integer.
Explanation / Answer
a) What is the statement P(1)?
P(1) is 1 = 20
b) Show that P(1) is true, completing the basis step of the proof.
In basis step we consider n=1.
We see that 1 = 20, we see that 1 can be written as sum of distinct powers of 2.
Hence, the statement P(1) is true.
c) What is the inductive hypothesis?
In the inductive hypothesis, we assume that for every positive value i can be written as sum of distinct powers of 2.
Thus, the statement P(j) is true for 1 j k, where n=j
Here k being a positive integer.
d) What do you need to prove the inductive step?
To prove the inductive step we would assume the inductive hypothesis as true.
And we would require to prove the statement is true when n=k+1, i.e (k+1) can be written as sum of distinct powers of two.
e) Complete the inductive step, identifying where you use the inductive hypothesis.
We would use the inductive hypothesis in the following proof.
We would consider two cases, when k+1 is odd positive integer and when k+1 is even positive integer.
Case 1: k+1 is an odd positive integer.
This makes k an even positive integer.
We use the inductive hypothesis here, assuming k can be written as sum of distinct powers of two.
20 is not included as it will make k odd.
Thus,
f(k+1) = f(k) + 20, which is sum of distinct powers of two.
Case 2: k+1 is an even positive integer.
This makes (k+1)/2 a positive integer(provided in the hint).
We use the inductive hypothesis here, assuming (k+1)/2 can be written as sum of distinct powers of two.
Thus,
f(k+1) = 2*f((k+1)/2)
As all powers in f((k+1)/2) are distinct, all powers in 2*f((k+1)/2) will also be distinct.
f) Explain why these steps show that this formula is true whenever n is a positive integer.
We have completed both the basis step and the inductive step, so by the principle of strong induction, the
statement is true for every integer n.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.