You can use induction on the quotient, that is you prove the base case, that is
And then you prove that for implies that (inductive step)
To prove this you will need the results you have proven.
Of course it may be done in other ways.
Take this matrix satisfies: for all (if you define to be 1) -this is an easy induction-
Now it is easy to see that: (just use the definition of the Fibonacci Numbers) thus:
But note that if 2 matrixes commute (i.e. ) , then we have: (The typical combinatorial proof of the Binomial Theorem)
Thus: and now read off the entries: which is a multiple of - since -