Final answer:
Using strong induction, we can prove that every positive integer can be written as a sum of distinct powers of two, starting with the base case of 1 and assuming it holds for all numbers up to k to establish it for k+1.
Step-by-step explanation:
We can show that every positive integer can be written as a sum of distinct powers of two using strong induction. First, we establish our base case: the number 1, which is equal to 2°. This serves as our starting point and is trivially true.
Assuming that every positive integer up to and including some integer k can be expressed as a sum of distinct powers of two, we now need to show that k+1 can also be written in this way. If k+1 is not a power of two itself, then it must be the sum of the largest power of two less than k+1 (say 2^n) and some remainder. This remainder must be less than 2^n and by our inductive hypothesis, this remainder can be expressed as a sum of distinct powers of two, none of which are 2^n or greater since that would exceed the remainder. Thus, k+1 is the sum of 2^n and the sum of distinct powers of two that make up the remainder, hence satisfying our induction step.
This process can be repeated for every integer, proving the assertion by strong induction.