# 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) > 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!

• In your proof, you seem to have missed the "+3" in $T(n)=T(n-1)+T(n-2) +3$. – Rick Decker Jan 30 '16 at 16:26
• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. – Raphael Jan 30 '16 at 16:54
• "the running time is exponential, i.e. $T(n) ≥ 1.41^n$" -- that is not a valid sentence. It is sufficient to show $T \in \Omega(c^n)$ for any $n$. – Raphael Jan 30 '16 at 16:57
• @Raphael Thanks for your input! I edited my question, hope that it is better! In your last comment, don't we also need restrictions on c? And would it still be accurate to just want to prove that $T(n) \ge 1.41^n$? (This problem originally came from my professor!) – GessaGessa Jan 31 '16 at 3:49
• @GessaGessa We need $c>1$ -- that's sufficient for exponential. Maybe your prof wants you to prove somethings stronger -- $\geq 1.41^n$ -- or they intended that as a hint towards a possible ansatz. In either case, "i.e." ("that is") is the wrong choice of words. But well, nitpick. – Raphael Jan 31 '16 at 10:55

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.

• What does the $T'$ mean? Is that a way of simplifying $T(n-1) + T(n - 2)$? Sorry to ask so many questions! – GessaGessa Jan 31 '16 at 3:55
• @GessaGessa I define $T'$ with the sole purpose of 1) getting $T \geq T'$, 2) $T'$ still being of exponential growth and 3) $T'$ being easier to determine (in closed form) than $T$, i.e. it should have an easier recurrence. Picking $T'$ is a creative step -- here I observed that $T(n-1) > T(n-2)$ and that the resulting recurrence would lead to $2^\_$ -- that is there is no "mechanic" dependence on the recurrence for $T$. Different $T$, different ideas. – Raphael Jan 31 '16 at 10:57
• It's much clearer to me now, thanks for all your help! I'm going to go see if I can work out the formalities on my own. – GessaGessa Jan 31 '16 at 23:25