CSC236

Problem Set 1:

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)

Sale!

# CSC236 Problem Set 1

$30.00

## Reviews

There are no reviews yet.