Let Fibn be the nth Fibonacci number Fib0 0 Fib1 1 Fibn F

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

Solution

1)induction step

put n=11 in equation

1.5^11=86.49

1.7^n=342.7

as this fib(11)=89 so

86.49<89<342.7

so

1.5^n<fib(n)<1.7^n

2) we assume this is true for k

1.5^k<fib(n)<1.7^n

3) we try to prove for k+1 using k

1.5^k+1<fib(k)<1.7^k+1( we have to proof)

rewriting above equation

1.5^k+1 can be written as 1.5^k*1.5

1.7^k+1 can be written as 1.7^k*1.7

as we know

1.5^k<fib(k)<1.7^k

as

1.5<1.7

multiplying left hand side with smaller no(1.5) then multiplying right hand side with larger number (1.7) would not change the sign of equation

so

1.5^k*1.5<fib(k+1)<1.7*1.7^k

hence proved