The powers of a function f: A → A are defined recursively byDefine the Fibonacci sequence...

The powers of a function f: A → A are defined recursively by

Define the Fibonacci sequence by f1 = f2 = 1, fn+1 = fn + fn−1 for n ≥ 2.

(a) Prove that gcd(fn+1, ƒn) = 1 for all n ≥ 1.

(b) Prove that ƒn = fn−m+1 fm + fn−m fm−1for any positive integers n and m with n > m > 1.

(c) Prove that, for any positive integers n and m, the greatest common divisor of fn and fm is fgcd(n, m).