March 6, 2007

**Printed Name:**________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."

**Signature:**___________________________________________

Prove the following statement using strong induction: Every positive integer can be written as the sum of unique powers of 2. (*clarified statement after discussion in class*) For example:

- 1 = 2^0
- 2 = 2^1
- 3 = 1 + 2 = 2^0 + 2^1
- 4 = 2 + 2 = 2^2
- 5 = 1 + 4 = 2^0 + 2^2

Let P(n) be the statement that n can be written as the sum of unique powers of 2.

- (1 pt) Base case: State and prove correct P(1) and P(2).

- (1 pt) Inductive Step: What is the inductive hypothesis?

- (2 pts) Rest of inductive step: Prove P(k+1).
*Hint:*Consider two cases, when k+1 is even and when it is odd. When k+1 is even, note that (k+1)/2 is an integer.

- (1 pt) Why doesn't regular induction work for this proof?