Getting a tighter upper bound on the following function
Let's count how many times we have to make a call into fib for each value of n. Let's call that number $f(n)$.

Then:

$$
\begin{align}
f(0) &amp;= 1 \\
f(1) &amp;= 1 \\
f(n) &amp;= 1 + f(n-1) + f(n-2) \qquad \textrm{(for $n &gt; 1$)}
\end{align}
$$

The first several values for $f$ are then 1, 1, 3, 5, 9, 15, 25, 41, 67, etc.

It turns out that if you add one to $f$ and half the result,(*) you get the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, etc.

That is, $f(n) = 2\cdot\textrm{fib}(n+1) - 1$

Since it is well known that the Fibonacci function is $O\left((\frac{1+\sqrt{5}}{2})^n\right)$, so is $f(n)$.

Note that since $\frac{1+\sqrt{5}}{2} \approx 1.618 &gt; 1.6$, the book is actually technically incorrect when it says that $O(1.6^N)$ is an upper bound, and should be corrected to say $O(1.62^N)$ or something similar.



(*) Okay, I kind of pull that out of a hat. As for how to mentally jump from a recursion that's almost like one you know but off by a constant (as in this case, the recursion formula for $f$ looked like the recursion for fib but had that annoying $1+$ at the beginning) one technique is to say:

"What if $g$ were something that obeyed fib's  recursion rule, and $f(n) = g(n) + C$ for some constant $C$. What happens when I substitute that into my recursion equation?"

You then end up with:

$$ g(n) + C = 1 + g(n-1) + C + g(n-2) + C $$

Using $g(n) = g(n-1) + g(n-2)$, you find that $C$ is $-1$. From that you see "Oh, $1+f(n)$ should look kind of like the Fibonacci series, but it starts with "2, 2", so..." (and then it's straightforward to write a formula for $f(n)$).