Bonus Question 1

worth 10 bonus wiki points

The Question

This question is actually Problem 3.3.2 in Chapter Zero. It's a beautiful application of complete induction, and one that illustrates the differences between complete and ordinary induction quite nicely. The problem here is (of course) to prove the theorem below, and to do so using complete induction.

Theorem. Every positive integer can be expressed as the sum of distinct powers of two.


The Solution

Proof:

P1: Let $x$ be a positive integer.
P2: First suppose $x=1$.
P3: Then x is equivalent to $2^0$.
P4: So the statement is true when $x = 1$ because $2^0$ is a sum with only one term.
P5: Now assume the statement is true for all integers between 1 and n; that is, every integer j where 1 is less than or equal to j is less than or equal to n can be expressed as the sum of distinct powers of two.
P6. If x+1 can be expressed as the sum of distinct powers of two, the statement is true for x+1.


Hints/comments/questions

  • If you want to get a sense of what it means for an integer to be expressed as the sum of distinct powers of two, you can find lots of examples on page 31 of Chapter Zero. In particular, the word "distinct" is very important — without it, we could just write $n=\sum_{i=1}^n 2^0$ and we'd be done!
  • Add any questions or comments here, or make a contribution to the solution above…
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License