Thread: Strong Induction Problem

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

I know for the inductive step I should seperately consider the case where k + 1 is even and where it is odd, so when it is even (k + 2) / 2 is an integer. Where would I proceed from here?

Originally Posted by aaronrj

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

I know for the inductive step I should seperately consider the case where k + 1 is even and where it is odd, so when it is even (k + 2) / 2 is an integer. Where would I proceed from here?

Say that can be written as exponents of two. Now if is even then set which is a sum of exponents of two. Multiply through both sides by and you have that is a sum of exponents of two. And if is odd then set which is a sum of exponents of two. Multiply through both sides by and add to get is a sum of exponents of two.