1. ## 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?

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