Final answer:
To show that every positive integer n can be written as a sum of distinct powers of 2, we can use mathematical induction. By considering the cases where n is even and odd separately and using the fact that (n-1)/2 is an integer when n is even, we can prove that every positive integer n can be expressed as a sum of distinct powers of 2.
Step-by-step explanation:
To show that every positive integer n can be written as a sum of distinct powers of 2, we can use mathematical induction. First, let's consider the base case where n = 1.
The sum of distinct powers of 2 for n = 1 is simply 20 = 1, which is true. Now, assuming that the statement is true for some positive integer k, we need to show that it holds for k + 1. If k is even, we can express it as the sum of powers of 2 as k = 2a1 + 2a2 + ... + 2am. Then, for k + 1, we can write it as (2a1 + 1) + 2a2 + ... + 2am.
Since 2a1 + 1 is odd, it can be expressed as a sum of distinct powers of 2 as shown in the previous step. If k is odd, we can write it as k = 2a1 + 2a2 + ... + 2am. Then, for k + 1, we can write it as (2a1 + 1) + (2a2 - 1) + 2a3 + ... + 2am. Again, the expression 2a1 + 1 is odd and can be expressed as a sum of distinct powers of 2.
Therefore, by mathematical induction, we have shown that every positive integer n can be written as a sum of distinct powers of 2.