For all recurrences, assume that T(1)=1, if no base case is given. 

 Let Fib(n) be the n-th Fibonacci number. Fib(0) = 0, Fib(1) = 1. Fib(n) = Fib(n-1) + Fib(n-2), for n > 1. Prove by induction the following: 1.5^n < Fib(n) < 1.7^n, for n >= 11. [Fib(11)=89, Fib(12)=144].