Prove by induction that the running time of recursive Fibonacci is exponential This example followed from a Fibonacci algorithm in class. The professor showed us how to compute $T(n) = T(n-1) + T(n-2) + 3$, but left this step for us to prove, so I decided to attempt to prove it! But I am finding it difficult to fully understand how to prove things involving lower and upper-bounds. After looking up many resources including some things from Stanford, this is what I have been able to come up with:

Let $T(n) =$ time for $fib1(n)$, where $T(n) = T(n-1) + T(n-2) + 3$

Claim: For $n \ge 6$, the running time of $fib1(n)$ is exponential, i.e $T(n) \ge (1.41)^n$ 

Base Case: $$T(6) = 8 \ge (1.41)^6 = 7.86$$
               $$T(7) = 13 \ge (1.41)^7 = 11.08$$

Inductive Hypothesis: Assume that for an arbitrary n, $T(n) \ge (1.41)^n$

Prove $T(n+1) \ge (1.41)^{n+1}$: 
$$T(n+2) = T(n+1) + T(n) + 3$$
$$\ge 1.41^n + 1.41^{n+1} \text{  [By the I.H]}$$ 
$$ = (1.41^n)(1+ 1.41) &gt; 1.41(1.41)^n$$

Thus, the running time of $fib1(n)$ is $\Omega{(1.41^n)}$

Edit:

I'm not entirely sure how correct this is, but I'm not as worried about that. My main concern is in the induction step, I feel like there is something I am missing conceptually. Specifically, how exactly can we be sure that $$T(n+2) = T(n+1) + T(n) + 3 \ge 1.41^n + 1.41^{n+1} $$ if we only know that $$T(n) \ge 1.41^n$$

I hope this clarifies my question. Thanks!
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.