Question

1. se strong induction to show that every positive integer, n, can be written as a sum of powers of two: 2⁰, 2¹, 2², 2³, .....
2. Give recursive definitions of the following sets.
   1. The set of all integers divisible by 5.
   2. The set of all ordered pairs, ( n, m ), where m = n mod 5.

Answer 1

Answer 1: * Using Strong Induction...

Note: For the inductive step, we are separately considering the case where k+1 is even and where it is odd. When it is even, note that (k + 1)/2 is an integer.

For example, if n = 3, assume n = k + 1, that means k + 1 = 3, then we can write k as and can write 1 as . (here 3 can be expressed a sum of two different powers of 2)

Let P(n) be the claim that n can be written as a sum of distinct powers of two.

We show that P(n) is true for all positive integers n.

Base step: Since 1 =    ..we have that P(1) is true.

Inductive hypothesis: Assume for a positive integer k that P(i) is true for all 1 ≤ i ≤ k.

Inductive step: We consider two cases, namely when k + 1 is even and when k + 1 is odd. If k + 1 is even, then (k + 1)/2 is an integer, and by the inductive hypothesis, we can express (k + 1)/2 by a sum of distinct powers of two. We can then multiply this sum by 2, which simply increases the exponent of each power of two by 1, so this is again a sum of distinct powers of two that is equal to k + 1. When k+1 is odd, we have that k is even. By the inductive hypothesis, we can express k as a sum of distinct powers of two. However, since k is even, the sum cannot contain Thus, we can add to this sum, which remains a sum of distinct powers of two, and equals k + 1.

Thus, in both cases, we can express k + 1 as a sum of distinct powers of two, so when P(i) is true for all 1 ≤ i ≤ k, we have that P(k + 1) is true. Since P(1) is true, this means that the claim is true for all positive integers, as shown by strong induction.

Answer 2: * Recursive Definition consists of two steps, basis step and recursive step.

a) The set of all integers divisible by 5

Basis Step: 1 S, 2 S, 3 S, 4 S, OR, 1, 2, 3, 4 S

Recursive Step : If   x S, then   x + 5 S.

b) The set of all ordered pairs, ( n, m ), where m = n mod 5

Basis Step: n S, m S.

Recursive Step: If  x S, then   x + 5 S.

**for a simpler explanation of answer 1, I have added 3 images, please find the handwritten images below: