Use strong induction to prove that any positive integer n can be written as a su
ID: 3681515 • Letter: U
Question
Use strong induction to prove that any positive integer n can be written as a sum of distinct powers of two, that is, as a sum of subset of integers 20 = 1, 21 = 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.]
Explanation / Answer
To prove that F(x) is true for all x, using strong induction on x we can use the foundation that by proving F(1) is true then by induction, when F(y) is true for any integer y. All we have to prove is that F(y+1) is also true when it comes to strong induction, we can assume that from F(1) to F(y) is true for every integer y, then it would suffice if we just prove that F(y+1) is true Example: Any amount in multiples of 10 greater than or equal to $120 can be compiled from $40 and $50 120 = 3 * $ 40 130 = 2 * $40 + $50 140 = 1 * $ 40 + 2 * $ 50 = 40 + 100 = $ 140 150 = 3 * 50 = 150 160 = 4 * 40 170 = 3 * 40 + 50 = 120 + 50 = 170 190 = 3 * 50 + 1 * 40 = 150 + 40 = 190 200 = 4 * 50 210 = 4 *40 + 50 160 + 50 = 210 310 = 3 * 50 + 4 * 40 = 150 + 160 = 310 applying strong induction for this case: The formula to make up x amount of dollars depends on making x – 40 dollars of value In other words, we first take x – 40 dollars and then add 40 dollars into it example, to make x = 200 dollars, $ 200 = 200 – 40 + 40 = 160 + 40 = 200 let a = $40 and b = $ 50 x + 10 >= 160, (x+10) – 40 >= 120 by inductive hypothesis, (x+10) – 40) = 40 a + 50 b Applying the same example for the problem in the question, any positive integer n can be written as a sum of distinct powers of 2 sum of subset of integers 20 20 = 2^4 + 2^2 = 16 + 4 = 20 21 = 2^4 + 2^2 + 2^0 = 16 + 4 + 1 = 21 22 = 2^4 + 2^2 + 2^1 = 16 + 4 +2 = 22 23 = 2^4 + 2^2 + 2^0 + 2^1 = 16 + 4 + 1 +2 = 23 24 = 2^4 + 2^3 = 16 + 8 = 24 Applying strong induction for this case, when n can be written in terms of powers of 2, then n-4 + 4 can also be written in the same fashion 24 – 4 + 4 = 24
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.