World's most popular travel blog for travel bloggers.

# [Solved]: Prove by induction that the running time of recursive Fibonacci is exponential

, ,
Problem Detail:

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) > 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 > 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.