Use strong mathematical induction to prove that Fn 2 n n 0S

Use strong mathematical induction to prove that Fn 2 n , n 0

Solution

The febonacci sequence is defined by F_n+1 = F_n-1 + F_n with F₀ = 0 and F₁ = 1.

Now we use strong mathematical induction to prove that Fn 2 ⁿ , n 0

Basis step :

for n = 0 , we have F₀ 2 ⁽⁰⁾ = 1 thus Fn 2 ⁿ , n = 0.

Induction step :

Assume that the inequality is true for n = k.

That is F_k 2 ^k where k 0

Now we prove that the inequality is true for n = k +1 .

Consider F_k+1 = F_k-1 + F_k

                                     2^{(k - 1)} + 2 ^k

                            < 2 ^k + 2 ^k

                            = 2( 2 ^k)

                            = 2 ^{k + 1}

Hence , F_k+1 2^{(k +1)}

Therefore, The inequality is true for n = k +1 if the inequality is true for n = k.

Hence , by strong mathematical induction it is true that Fn 2 ⁿ , n 0