1. Prove that 4n + 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=21=2
1011=23+21+20=11
110001 = 25 + 24 + 20 = 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:
a. 7 ∈ F
b. If u, v ∈ F, then u + v ∈ F
c. 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)
