1.  [8 marks] Number representation.

You may  (but are not required to) use results from part (a) in your solution for part (b), and you may use results from parts (a) and (b) in your solution for part (c).

(a)  [1 mark]

Let (bk − 1 ···b0)2 be a binary representation of a natural number, and a be a single bit. Prove: (bk − 1 ···b0a)2 = 2 · (bk − 1 ···b0)2 + a.

Hint: Remember that the notation (···)2 is just a shorthand for a certain summation—work directly with these summations.

(b)  [5 marks]

Let n ∈ N and let (b2n − 1 ···b0)2 be a binary representation of a natural number.

Use induction to prove that (b2n − 1 ···b0)2 − (b1b0)2 − (b3b2)2 −···− (b2n − 1b2n −2)2 is a multiple of 3. Hint: You may  (but are not required to) use the fact that ∀n ∈ N, 3 | 4n − 1.

(c)  [2 marks]

Let x be a natural number with a binary representation where the difference between the number of 1 bits with an even index and the number of 1 bits with an odd index is a multiple of 3.

Prove that x is a multiple of 3.

2.  [12 marks] Induction.

For m,n ∈ Z+, define P(m,n) to be:

the number of ways to write n = x1 + ··· + xm with x1,...,xm ∈ N is

(a)  [6 marks]

Prove each of the following statements.

i. ∀n ∈ Z+ ,P(1,n).

ii. ∀m ∈ Z+,P(m, 1).

iii. ∀m,n ∈ Z+ ,P(m,n + 1) ∧ P(m + 1,n) ⇒ P(m + 1,n + 1).

(b)  [2 marks]

Use the results from part (a) to prove P(2, 2) ∧ P(3, 3).

(c)  [3 marks]

For t ∈ Z+ with t ≥ 2, define Q(t) to be: ∀m,n ∈ Z+ ,m + n = t ⇒ P(m,n).

Prove, by Induction: ∀t ∈ Z+ ,t ≥ 2 ⇒ Q(t).

Hint: You may use the results from part (a) in your solution.

(d)  [1 mark]

Use the results from previous parts in this question to prove ∀m,n ∈ Z+ ,P(m,n).