Prove by induction that the running time of recursive Fibonacci is exponential
Observe that with

$\qquad  T(n) = T(n−1)+T(n−2)+3$

and

$\qquad T'(n) = 2 T'(n-2)$,

you have $T &gt; T'$ assuming similar anchors, in particular because both functions are non-decreasing. $T'$ solves to $T'(n) \approx 2^{n/2} \geq 1.41^n$.

I intentionally provide only a sloppy sketch; I'll leave the formal proof to the interested reader.