Problem Set 1 Solution

Description

1. Prove that 4ⁿ + 15n – 1 is divisible by 9 for all n ≥ 1, using simple induction.

(3 marks)

2. Consider binary strings that start with a 1. By interpreting the 1’s as specifying powers of 2, these strings are called binary representations of positive integers. For example:

10=2¹=2

1011=2³+2¹+2⁰=11

110001 = 2⁵ + 2⁴ + 2⁰ = 49

a) Prove that every natural number n ≥ 1 has a binary representation. (4 marks)

b) Prove that the binary representation is unique. (4 marks)

3. Consider the Fibonacci-esque function g:

1 if n=0

3 if n=1

g(n – 2) + g(n – 1) if n > 1

Use complete induction to prove that if n is a natural number greater than 1, then 2n/2 ≤ g(n) ≤ 2n.

(7 marks)

4. Given the function L(n) below:

int L(n) :

if n < 7 : return 0

else : return 1 + L(n/7)

find a recurrence that expresses the time complexity, T(n) of L(n), in terms of n. Find a closed form for your recurrence and prove it is correct. Your expression should assign a constant to operations that do not depend on n.

(6 marks)

5. Let set F be recursively defined as follows:

5. 1. 7 ∈ F

5. 2. If u, v ∈ F, then u + v ∈ F

5. 3. Nothing else is in F

Use structural induction to prove that ∀w ∈ F, w mod 7 = 0, i.e., all elements in F are divisible by 7.

(6 marks)