# Fibonacci Numbers - proof.

• Nov 25th 2007, 08: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 \$\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. :)
• Nov 25th 2007, 08:59 AM
CaptainBlack
Quote:

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
• Nov 25th 2007, 09:08 AM
WWTL@WHL
Quote:

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.