Relations and Functions (Home Work)

Question

The Fibonacci sequence F₀, F₁, F₂, F₃, ... is an infinite sequence defined by the two initial values F₀ =0, F₁ =1, and the rule F_k = F_k-2 + F_k-1  for all k ≥ 2.
Let Μ = [1  1
              1  0]

(a) Write down F₂, F₃, F₄, F₅ and F₆.

(b) Calculate M², M³, M⁴ and M⁵.

(c) Notice that M¹ = [F₂  F₁
                                    F₁  F₀] Write down M² in terms of F₁, F₂ and F₃.

(d) Write down M³ in terms of F₂, F₃ and F₄.

(e) Write down M⁴ in terms of F₃, F₄ and F₅.

(f) Make a conjecture about the general form of Mⁿ. In other words, write down an expression for Mⁿ in terms of F_i which generalizes your answers to parts (c), (d) and (e).

(g) Prove that your answer to part (f) is true for all K ≥ 0 by using mathematical induction.

Answer 1

This question was addressed earlier today.