F n isin n define hn to be the hypothesis that both fn

Question

Math 104: Homework 1-

1. The Fibonacci numbers are defined by F₀ = 0 and F₁ = 1, and

F_n+1 = F_n + F_n-1

for n ∈ N. Let the golden ratio be defined as ? = (1+√5/2).

(a) Show that ?² = 1 + ?.

(b) Let f(n) = (?ⁿ - (1 - ?)ⁿ/√5).

For n ∈ N, define H_n to be the hypothesis that "both F_n = f(n) and F_n-1 = f(n - 1)". Apply mathematical induction to prove that H_n is true for all n ∈ N, and deduce that F_n = f(n) for all n ∈ N ∪ {0}. [Hint: it is simpler to carry out the algebra in terms of ? and use the identity in (a), as opposed to calculating explicitly in terms of (1 + √5)/2.].