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.
__________________________________________________ ______________
Question:
Let be the Fibonnaci numbers, defined by,
for
Prove that for all we have
__________________________________________________ _____________
My attempts:
I was considering two different methods to tackle this problem.
__________________________________________________ _____________
Method 1:
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.
Hence
When n=0,
__________________________________________________ ______________
Method 2:
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.
__________________________________________________ ______________
My question:
Is method 1 a satisfactory proof? Are there any ways I can improve it?
Thanks a lot fellas.