Final answer:
Every positive integer can be expressed as a sum of distinct powers of 2 using strong induction, by assuming the statement is true for all integers less than n and showing it holds for n.
Step-by-step explanation:
Proof by Strong Induction
To show that every positive integer n can be expressed as a sum of distinct powers of two, we'll use the principle of strong induction. For strong induction, we assume p(k) is true for all values of k less than n and use this to show that p(n) is also true. The proposition p(n) states that a positive integer n can be written as a sum of distinct powers of 2.
Base Case: For n=1, p(1) is trivially true since 1 is a power of 2 (2^0).
Inductive Step: Assume p(k) is true for all positive integers k such that k < n. We want to show that p(n) is also true, meaning n can be written as a sum of distinct powers of 2. If n itself is a power of 2, the proposition is immediately true. Else, let m be the largest power of 2 less than n. By our inductive hypothesis, n - m is a sum of distinct powers of 2, none of which can be m since m is the largest power of 2 less than n. Therefore, n can be expressed as m plus a sum of distinct, smaller powers of 2, which are also different from m, completing the proof.