The Fibonacci numbers Fn are defined by FO 1 F1 1 and Fn

The Fibonacci numbers F_n are defined by F-O = 1, F_1 = 1, and F_n = F_n_1 + F_n_2 when n Greaterthanorequalto 2. Find F_2, F_3, F_4, and F_5. Prove that F_n Greaterthanorequalto 2^n for all integers n Greaterthanorequalto 0. Note that this uses strong induction, and there are two base cases to check

Solution

4. The Fibonacci numbers are defined by F₀ = 1, F₁ = 1 and F_n = F_n-1 + F_n-2 when n 2

(a) F₂ = F₁ + F₀ = 1 + 1 = 2

F₃ = F₂ + F₁ = 2 + 1 = 3

F₄ = F₃ + F₂ = 3 + 2 = 5

F₅ = F₄ + F₃ = 5 + 3 = 8

(b) To prove that F_n 2ⁿ for all integers n 0

Proof by induction:

When n = 0, F₀ = 1 2⁰

When n = 1, F₁ = 1 2 = 2¹

When n = 2, F₂ = 2 4 = 2²

When n = 3, F₃ = 3 8 = 2³

Hence, the proposition is true for all non-negative integers n 3

Suppose that the proposition F_n 2ⁿ is true for n = k and for all smaller values of k, where k is a fixed positive integer > 3.

Then, F_k 2^k and F_k-1 2^k-1

Adding the inequalities gives, F_k+1 = F_k + F_k-1 2^k + 2^k-1 < 2^k + 2^k = 2. 2^k = 2^k+1

So we get, F_k+1 2^k+1

In other words, the proposition is true for n = k + 1 when it is true for n k. Therefore by theory of induction, we say that the proposition F_n 2ⁿ is true for all positive integers. (Proved)