# Sample Exam Problems, CPSC 500-101, Fall 2013

1. First Week and Chapter 0
1. Let A : ℕ satisfy
• A(n)=A(n-1)+A(n-2)+1 for all n>2 .
Let Let T : ℕ satisfy
• T(n)=T(n-1)+T(n-2)+Overhead(n), for all n>2 ,
where Overhead(n) is a function of positive integers n for which
• Overhead(n) ≥ 1, for all n.
Use induction on n to show that if
• T(1) ≥ A(1), and T(2) ≥ A(2),
then for all n we have
• T(n) ≥ A(n).
Explain the relevance of this to computing Fibonacci numbers in a (pretty awful) recursive algorithm, where each function call involves some (presumably polynomial time) overhead, but surely must perform one addition.

2. The Fibonacci numbers are given by f(1)=f(2)=1, and f(n) = f(n-1) + f(n-2) for all n>2. Show, by induction, that for any n>1, f(n-1) and f(n) are relatively prime (you may use the fact that if a and b are integers, then a is relatively prime to b iff b is relatively prime to a+b.

3. The Fibonacci numbers are given by f(1)=f(2)=1, and f(n) = f(n-1) + f(n-2) for all n>2. Show, by induction, that for any n > 1,
• f(n)f(n)-f(n-1)f(n+1)
is -1 if n is even, and +1 if n is odd.

4. Prove by induction on n that
• 1+4+9+16+...+n^2 = n(n+1)(2n+1)/6.

5. The Fibonacci numbers are given by f(1)=f(2)=1, and f(n) = f(n-1) + f(n-2) for all n>2. Show, by induction, that for any integer n > 1,
• 2^(n-1) ≥ f(n).

6. A merge sorting algorithm takes time T(n) given by T(1)=5, and
• T(n) = 2 T(n/2) + 5n
(if n is not even we need to use the floor and ceiling functions, but let is ignore this here). Show that if n is a power of two, namly 2^m, then
• T(n) = 5n (m+1) = 5 n (log(n)+1),
where the logarithm is base 2.

7. The Fibonacci numbers are given by f(1)=f(2)=1, and f(n) = f(n-1) + f(n-2) for all n>2. Show, by induction, the exact formula for f(n) in Exercise 0.4 of the text.

2. Chapter 1
3. Chapter 2
4. Etc.