Where does O(2ⁿ) come from? Watch the recursion tree.

Step through fib(n) in the order the calls actually happen. The tree on the left grows; the derivation on the right assembles itself from what you see.