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. (1 pt) Base case: State and prove correct P(1) and P(2).
   
   
   
   
   
   
   
   
2. (1 pt) Inductive Step: What is the inductive hypothesis?
   
   
   
   
3. (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.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
4. (1 pt) Why doesn't regular induction work for this proof?