Question

Fibonacci Sequence:

F(0) = 1, F(1) = 2, F(n) = F(n − 1) + F(n − 2) for n ≥ 2

(a) Use strong induction to show that F(n) ≤ 2^n for all n ≥ 0.

(b) The answer for (a) shows that F(n) is O(2^n). If we could also show that F(n) is Ω(2^n), that would mean that F(n) is Θ(2^n), and our order of growth would be F(n). This doesn’t turn out to be the case because F(n) is not Ω(2^n), and thus not Θ(2^n). But it is true that F(n) ≥ (3/2)^n for all n ≥ 0. Use induction (or strong induction) to prove this.

Answer 1

a) Answer:

Base case: We know that,

F(1) = 1 < 2 ^{^} 1= 2

F(2) = 1 < 2 ^ 2 = 4

Induction step: In strong induction method, if n is a positive integer such that F(1), F(2) , ……..F(n) are all true, then F(n+1) is also true.

   Now suppose that F(n) < 2^ n for all n >= 0

Given, F(n) = F(n – 1) + F(n -2)

Then, F(n+1) = F(n) + F(n-1) <= 2.F(n)

<= 2. 2 ^ n

<= 2 ^ (n+1)

Hence, F(n) <= 2 ^ n for all n>=0

b) Answer:

From the above proof it is clear that F(n) <= 2 ^ n. That is F(n) is O(2 ^n)

Since, F(n) is not Ω(2 ^ n) and thus not Ѳ(2 ^ n)

Now we will prove by strong induction method F(n) >= (3/2) ^ n for all n>=0

Base case:

                F(1) = 1 < 2 ^{^} 1=2

F(2) = 1 < 2 ^ 2= 4

                                Induction step:

                                                Suppose that F(n) >= (3/2) ^ n for all n>=0

                                                Then, F(n+1) = F(n) + F(n-1) >= (3/2) ^ n + (3/2) ^ (n -1)

                                                                                                      >= (3/2) ^ (n + 1)

                                                Hence, proved that F(n) >= (3/2) ^ n