Thread: Fibonacci Numbers - proof.

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.

Originally Posted by WWTL@WHL

Method 1:


Using Euclid's algorithm, we find that the remainder when is divided by is

Using Euclid's algorithm, we find that the remainder when is divided by is

RonL

Originally Posted by CaptainBlack

Using Euclid's algorithm, we find that the remainder when is divided by is

RonL

Right, so now I'm realy stuck. Any ideas on what to do?

EDIT:

We can write

so in Euclid's algorithm, the general form of stands with , , . It follows that q=1.

So

And , for n=0, is gcd(1,2) = 1.

So

But that can't be right because it seems that the remainder made no difference to the outcome. i.e. it might as well have been positive.