Solution: 2014 Winter Final - 11

Author: Michiel Smid

Question

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 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 5$, run algorithm $\Fib(n)$ and let $a_n$ be the number of times that $\Fib(4)$ is called.
Which of the following is true?

(a)

for all $n \geq 5$, $a_n = f_{n-1}$

(b)

for all $n \geq 5$, $a_n = f_{n-3}$

(c)

for all $n \geq 5$, $a_n = f_n$

(d)

for all $n \geq 5$, $a_n = f_{n-2}$

Solution

Base Case Analysis:
For $ n = 0 $ or $ n = 1 $, $ FIB(n) $ is called directly and returns $ n $.
For $ n \geq 2 $, the algorithm makes recursive calls to $ FIB(n-1) $ and $ FIB(n-2) $.
Recursive Call Analysis:
To find the number of times $ FIB(4) $ is called in $ FIB(n) $, we analyze the recursive structure of $ FIB $.
Each call to $ FIB(n) $ results in calls to $ FIB(n-1) $ and $ FIB(n-2) $.
Pattern Recognition:
Consider $ FIB(n) $ for different values of $ n $:
$ FIB(5) $ calls $ FIB(4) $ and $ FIB(3) $.
$ FIB(6) $ calls $ FIB(5) $ and $ FIB(4) $.
$ FIB(7) $ calls $ FIB(6) $ and $ FIB(5) $.
Recursive Counting:
Let $ a_n $ be the number of \times $ FIB(4) $ is called in $ FIB(n) $.
Observe that $ a_n $ satisfies the recurrence relation similar to the Fibonacci sequence:
$a_n = a_{n-1} + a_{n-2}$
Initial conditions are crucial:
$ FIB(4) $ is called 1 time in $ FIB(4) $.
$ FIB(5) $ calls $ FIB(4) $ directly once and $ FIB(3) $, which does not call $ FIB(4) $.
Connecting to Fibonacci Sequence:
The recurrence relation $ a_n = a_{n-1} + a_{n-2} $ with initial conditions $ a_4 = 1 $ and $ a_5 = 1 $ corresponds to the Fibonacci sequence shifted by 3:
$a_n = f_{n-3}$
Conclusion:
Therefore, the number of times $ FIB(4) $ is called in $ FIB(n) $ is given by the Fibonacci number $ f_{n-3} $:
$a_n = f_{n-3}$