Define the Lucas numbers as L1 = 1, L2 = 3, and Ln = Ln−1 + Ln−2 for n ≥ 3. (The Fibonacci numbers are a much more famous cousin of the Lucas numbers; the Lucas numbers follow the same recursive...

Define the Lucas numbers as L1 = 1, L2 = 3, and L_n
= L_n−1
+ L_n−2
for n ≥ 3. (The Fibonacci numbers are a much more famous cousin of the Lucas numbers; the Lucas numbers follow the same recursive definition as the Fibonacci numbers, but start from a different pair of base cases.) Prove the following facts about the Lucas numbers, by induction (weak or strong, as appropriate) on n:

5.59 (Ln) 2 = 5(fn) 2 + 4(−1)n (Hint: for Exercise 5.59, you may need to conjecture a second property relating Lucas and Fibonacci numbers to complete the proof of the given property P(n)—specifically, try to formulate a property Q(n) relating LnLn−1 and fnfn−1, and prove P(n) ∧ Q(n) with a single proof by strong induction

Exercise 5.59

For a k-by-k matrix M, the matrix Mn is also k-by-k, and its value is the result of the n-fold multiplication of M by itself: MM M. Or we can define matrix exponentiation recursively: M⁰
:= I (the k-by-k identity matrix), and Mⁿ+1 := M Mⁿ
. With this definition in mind, prove the following identity: