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.