# Thread: Fibonacci Numbers - proof.

1. ## 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. 2. Originally Posted by WWTL@WHL 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}$

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

RonL

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

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

EDIT:

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

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

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

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

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

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

#### Search Tags

fibonacci, numbers, proof 