CPSC 289 Sec 502: Quiz 6
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."


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:

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?