Question

Recall from class that the Fibonacci numbers are defined as follows: fo = 0,fi-1 and for all n fn-n-1+fn-2- 2, (a) Let nEN,n 24. Prove that when we divide In by f-1, the quotient is 1 and the remainder is fn-2 (b) Prove by induction/recursion that the Euclidean Algorithm takes n-2 iterations to calculate gcd(fn,fn-1) for n 2 3. Check your answer for Question 1 against this.

Answer 1

(a) Recall that for any two integers a and b, if we can get integers q and r with $0 \le r \le b-1$ ,such that a=bq+r, then q is the quotient and r is the remainder, when a is divided by b. Compare $f_n=f_{n-1}+f_{n-2}$ , with a=bq+r, here $0 \le f_{n-2} \le f_{n-1}$ , hence we get q=1 and $r=f_{n-2}$ , that is the desired quotient and remainder.

(b) Recall the Euclidean algorithm, to compute , for any two non negative integers. If a=b then gcd(a,b)=a. If $a\not= b$ , then we can assume (without loosing any generality ) that a>b. Then get q,r>0 with $0\le r\le b-1<b$ , such that $a=bq+r$ , Now repeating the process for the pair (b,r) and for that we will get a remainder less than r, then again repeat the process on r and the new remainder and repeat again until the remainder gets 0. This is the algorithm.

So for calculating , where   $f_n=f_{n-1}+f_{n-2}$ , for the initial step we get $f_{n-2}$ , similarly using the fact , in the first step we will get $f_{n-3}$ and so on.

Note that this process will stop when the remainder gets to zero. And each cases the remainder is of the form $f_{n-k}$ for some k, and this term is zero when n-k is zero.

So in the zero-th step we got $f_{n-2}$ , in the first step we get $f_{n-3}$ . Thus doing this on recursively we get at the i-th stage we will get the remainder $f_{n-2-i}$ , and for the remainder to get zero we have ${n-2-i}=0$ that is i=n-2.

Thus at the n-2 th stage the Euclidean algorithm will stop.

Feel free to put a comment if you have any doubts. Cheers!