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 $\displaystyle F_0, F_1, F_2, .....$ be the Fibonnaci numbers, defined by,

$\displaystyle F_0 = 1; F_1 = 1; F_n= F_{n-1} + F_{n-2}, $ for $\displaystyle n \ge 2 $

Prove that for all $\displaystyle n \ge 0 $ we have $\displaystyle gcd(F_{n+2}, F_n) = 1 $

__________________________________________________ _____________

__My attempts:__

I was considering two different methods to tackle this problem.

__________________________________________________ _____________

**Method 1:**

$\displaystyle F_{n+2} = F_n + F_{n+1} $

Using Euclid's algorithm, we find that the remainder when $\displaystyle F_{n+2} $ is divided by $\displaystyle F_n$ is $\displaystyle F_{n+1} $

And Euclidean algorithm says that for integers such that:

$\displaystyle a = bq + r $, $\displaystyle gcd(a,b)=gcd(b,r) $

In this scenario, $\displaystyle a = F_{n+2}, b = F_n, c = F_{n+1} $, which gives q=1.

Hence $\displaystyle gcd(F_{n+2}, F_n) = gcd(F_n,F_{n+1}) $

When n=0, $\displaystyle gcd(F_0, F_1) = gcd(1,1) = gcd(F_{n+2},F_n) = 1 $

$\displaystyle \Box$

__________________________________________________ ______________

**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. :)