# Strong Induction Problem

• Oct 30th 2008, 07:56 PM
aaronrj
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?
• Oct 31st 2008, 05:09 AM
ThePerfectHacker
Quote:

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 \$\displaystyle k<n\$ can be written as exponents of two. Now if \$\displaystyle n\$ is even then set \$\displaystyle k=\tfrac{n}{2}\$ which is a sum of exponents of two. Multiply through both sides by \$\displaystyle 2\$ and you have that \$\displaystyle 2k = n\$ is a sum of exponents of two. And if \$\displaystyle n\$ is odd then set \$\displaystyle k=\tfrac{n-1}{2}\$ which is a sum of exponents of two. Multiply through both sides by \$\displaystyle 2\$ and add \$\displaystyle 1\$ to get \$\displaystyle 2k+1=n\$ is a sum of exponents of two.