# Strong Induction Problem

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