# Fibonacci Numbers - proof.

• Nov 25th 2007, 09:38 AM
WWTL@WHL
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 $F_0, F_1, F_2, .....$ be the Fibonnaci numbers, defined by,

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

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

__________________________________________________ _____________

My attempts:
I was considering two different methods to tackle this problem.
__________________________________________________ _____________

Method 1:
$F_{n+2} = F_n + F_{n+1}$

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

And Euclidean algorithm says that for integers such that:
$a = bq + r$, $gcd(a,b)=gcd(b,r)$

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

Hence $gcd(F_{n+2}, F_n) = gcd(F_n,F_{n+1})$
When n=0, $gcd(F_0, F_1) = gcd(1,1) = gcd(F_{n+2},F_n) = 1$
$\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. :)
• Nov 25th 2007, 09:59 AM
CaptainBlack
Quote:

Originally Posted by WWTL@WHL
Method 1:
$F_{n+2} = F_n + F_{n+1}$

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

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

RonL
• Nov 25th 2007, 10:08 AM
WWTL@WHL
Quote:

Originally Posted by CaptainBlack
Using Euclid's algorithm, we find that the remainder when $F_{n+2}$ is divided by $F_{n+1}$ is $F_{n}$

RonL

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

EDIT:

We can write $F_{n+1} = F_{n+2} - F_n$

so in Euclid's algorithm, the general form of $a = bq+r$ stands with $a = F_{n+1}$, $b = F_{n+2}$, $r = - F_n$. It follows that q=1.

So $gcd(F_{n+1}, F_{n+2}) = gcd(F_{n+2}, F_n)$

And $gcd(F_{n+1}, F_{n+2})$, for n=0, is gcd(1,2) = 1.

So $gcd(F_{n+2}, F_n) = 1$

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