Afternoon guys :) I'm considering 2 ways of approaching this question. One is significantly easier than the other, but I wanted to know if it is a valid method - or rigorous and formal enough for a proof. Thanks.
Let be the Fibonnaci numbers, defined by,
Prove that for all we have
I was considering two different methods to tackle this problem.
Using Euclid's algorithm, we find that the remainder when is divided by is
And Euclidean algorithm says that for integers such that:
In this scenario, , which gives q=1.
Proceed by Induction. I won't bother posting my attempt for this yet, since if I can prove this without induction (i.e. like above) then there isn't much need in a longer proof - unless of course the first one isn't formal enough.
Is method 1 a satisfactory proof? Are there any ways I can improve it?
Thanks a lot fellas. :)