MAT 230 Multiply choice questions
1. True or False? Recursion functions can be proven using mathematical induction.
a. True
b. False
2. Fibonacci numbers are defined as: for n > 1. The first five Fibonacci numbers are: 1, 2, 3, 5, 8. What is the next Fibonacci number?
a. 11
b. 13
c. 15
d. None of the above
3. Find f(4) if f is defined recursively by: f(0) = f(1) = 1 and for n > 1.
a. 1
b. 2
c. 29
d. 33
4. True or False? The following proposed definition of a recursive function is valid for n > 1: f(0) = 0, f(1) = 1, f(n) = 2f(n+1).
a. True
b. False
5. An investor begins to save in 1990 with $500. Each year, the savings increases 10% over the year before, and the investor contributes another $100. Write a recurrence relation and initial conditions on sn, the amount of savings n years after 1990. Use this relation to determine the amount saved by 1994.
a. $1,196.15
b. $ 996.50
c. $ 732.05
d. $1,415.77
6. True or False? In programming a recursive algorithm, the algorithm must call itself with smaller input.
a. True
b. False
7. What is the result of the following recursive algorithm?
procedure unknown(n:positive integer)
if n = 1 then
unknown(n) := 1
else
unknown(n) := unknown(n-1) + n
end procedure
a. n + n-1 = 2n - 1
b. n
c. sum of n positive integers
d. zero
8. Find the sequence for the recursive formula: ,
a. -4, 14, -4, 14, ...
b. -4, 9, -3, 11, ...
c. -4, 5, 10, -4, 5, 10, ...
d. not a recursive formula
9. Find the sequence for the following closed formula: for n = 1, 2, 3.
a. 5, -9, 5, 9
b. 6, 14, 86, 734
c. -4, 14, -4, 14
d. -4, -4, -4, -4
10. Consider the recursive algorithm for Fibonacci numbers:
procedure fib(n:nonnegative integer)
if n = 0 then
fib(0) := 0
else if n = 1 then
fib(1) := 1
else
fib(n) := fib(n-1) + fib(n - 2)
end procedure
How many additions does it take to find f(7), the eighth Fibonacci number?
a. 8
b. 10
c. 6
d. 20