Practice By Tag: Counting Bitstrings of Length n

Question: 2014 Winter Midterm - 12

1 . The Fibonacci numbers are defined as follows: $f_0 = 0$, $f_1 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for $n \geq 2$.
Consider again the recursive algorithm $\Fib$, which takes as input an integer $n \geq 0$:

$\mathbf{Algorithm}\ \Fib(n)\mathrm{:}$
$\mathbf{if}\ n = 0\ \mathrm{or}\ n = 1$
$\mathbf{then}\ f = n$
$\mathbf{else}\ f = \Fib(n - 1) + \Fib(n - 2)$
$\mathbf{endif};$
$\mathbf{return}\ f$

For $n \geq 3$, run algorithm $\Fib(n)$ and let $a_n$ be the number of times that $\Fib(2)$ is called.
Which of the following is true?

(a)

For $n \geq 3$, $a_n = -1 + f_n$

(b)

For $n \geq 3$, $a_n = f_n$

(c)

For $n \geq 3$, $a_n = f_{n - 1}$

(d)

For $n \geq 3$, $a_n = f_{n + 1}$