# Fibonacci Sequence recursion algorithm and the time complexity

I am reading a free book on algorithms

http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf

and on page 13 it says

"Compare this to the recurrence relation for Fn: we immediately see that T(n) ≥ Fn"

I do not understand how they know that T(n) ≥ Fn

if someone could explain it to me it would be much appreciated. here is a picture of the information needed

• Thank you for the response, we discourage the image content, because it is not searchable, but yes, it is better text > image > link. – Evil Sep 9 '17 at 19:12
• @cmptUser Not much better, no. Now there's far too much material. – David Richerby Sep 9 '17 at 20:07
• It's kinda weird, that this algorithm is called bad, because exponentiation takes exponential amount of resources. – rus9384 Sep 9 '17 at 20:37

You can prove that $T(n) \geq F_n$ by induction. For $n = 0$ and $n = 1$ we have $T(n) \geq 1$ and $F_n \leq 1$. Suppose that the claim holds for $n-1$ and $n-2$. Then $$T(n) = T(n-1)+T(n-2)+3 \geq F(n-1)+F(n-2) = F(n).$$