The kth powers of the Fibonacci numbers satisfy a linear homogeneous recurrence relation of order k + 1 with integer coefficients.

Let’s consider one of the most famous sequences of numbers, the Fibonacci sequence, named after Leonardo of Pisa, a.k.a. Leonardo Fibonacci (1170-1250). The Fibonacci sequence {F0, F1, F2, . . .} is defined recursively by the initial values

F0 = 0, F1 = 1,

and the recurrence relation

Fn = Fn−1 + Fn−2, for n ≥ 2.