6
$\begingroup$

I think Lamé's Theorem is beautiful and really want to understand the proof.

I am new to proofs, but after reading over the proof of Lamé's Theorem (and failing to understand it), I feel that I am capable of understanding it because it contained terms such as Fibonacci numbers, logarithms (base 10 and e), and the golden ratio - all of which I am familiar with. Although I understand those terms, I just need a little help with the reasoning.

A step-by-step analysis of the proof would help me tremendously!

Here is the proof I read.

$\endgroup$
  • $\begingroup$ Perhaps it is better to tell us what part(s) you don't understand, and we can help you from there. $\endgroup$ – RghtHndSd Jul 25 '13 at 19:12
6
$\begingroup$

Ok, well. One of the best way to understand a proof is to reproduce it via free recall after glancing over the basic components of the proof.

So the theorem is:

Let a and b be integers; let $a>b$. Applying Euclidean Algorithm to find the GCD will take n steps. The theorem says that if b has $d$ digits, then $n\leq 5d$.

The components are Fibonacci's number and Euclidean Algorithm, and some other things.

First, let us see why the theorem might be true.

Well, first, let us look at Euclidean Algorithm. What does it do? We look in wikipedia and sees that

Given $a, b$, we first find $b_1 = a\mod b$, and then set $a_1=b$.

At the $i$'th step, we find $b_{i} = a_{i-1} \mod b_{i-1}$ and then set $a_{i} = b_{i-1}$. The algorithm ends at step n when we find that $b_n=0$.

Well, does the theorem make any sense? Should there be a max limit to the number of steps the algorithm will take.

Well, yes, of course.

First of all, we note that $b_{n-1} \geq 1$.

Second, let us look at an example. Let $b_{i-2} = 30 = {a_{i-1}}$, what is the highest possible $b_i$? Well, let us say that $b_{i-1}$ can be anything. What will give the greatest $b_i$?. Well, the whole point is, $30 \pmod {b_{i-1}}$ cannot be greater than $14$. So, we can see that $b_i < \frac{1}{2}b_{i-2}$.

This already gives us a bound. You see, $2^4>10$, so $b_i$ has at least one less digit than $b_{i-8}$.

Now, we want a stronger bond. The other important component is the Fibonacci numbers.

Let us look at them.

1,2,3,5,8,13,21,34,55,89, 144 ...

We can see immediately that for every number, if you look 5 numbers over, there is at least one more digit.

So, if we can relate our thing to the Fibonacci's sequence, that'd be great.

Well, we can.

We already said that $b_n = 0$. The smallest value $b_{n-1}$ could be is $b_{n-1} = 1$. (In case you need to justify this, consider the other possibilities. It must be an integer. If it is 0, then the algorithm would have ended at the $n-1$ step. But we already designated n to be the step at which it ends at.) Well, how about $b_{n-2}$?

Well first, we see that $b_i<b_{i-1}$. This should be obvious since $b_i$ is the remainder of something divided by $b_{i-1}$.

So, the smallest $b_{n-2}$ could be is $2$.

Now, let us proceed.

What is the smallest $b_{n-3}$ could be. Well, to get $b_{n-1}$, we divided $a_{n-2} = b_{n-3}$ by $b_{n-2}$ and found the remainder. Therefore, $a_{n-2}=b_{n-3} = c\times b_{n-2}+b_{n-1}$. This is obviously greater or equal to just $b_{n-2}+b_{n-1}$.

Now, we can generalize this, can't we. Let us say we know that $b_i$, and $b_{i-1}$. Well, we know that $b_i = b_{i-2} \mod b_{i-1}$, so $b_{i-2} = cb_{i-1}+b_i \geq b_{i-1} + {b_i}$. $$$$$$$$

What does this look like? Why, the Fibonacci's sequence!

COOL!

Ok, so it seems like the $b_{n-j}$ cannot be less than the jth number in the sequence.

There is subtle point here. We have not proved it. We have only proved that $b_{n-1} \geq 1$, $b_{n-2}\geq 2$, and that $b_{i-2}\geq b_{i-1}+b_{i} $.

We want to prove that the least possible value of $b_{n-j}$ is the jth number in the sequence. So...

We still need to prove that the least possible value of $b_{i-2}$ is greater than the sum of the least possible value of $b_{i-1}$ and $b_{i}$. This is pretty easy to prove.

For any $b_{i-2}$, we have that $b_{i-2} \geq b_{i-1} + b_{i} \geq \min(b_{i-1})+ \min(b_{i})$. As such, $\min (b_{i-2})\geq \min(b_{i-1})+ \min(b_{i})$.

So now, we prove that $b_{n-j}$ is greater or equal to $F_j$ the $j'$th term of the Fibonacci sequence.

It is true for $j=1$ and $j=2$. $b_{n-1}>\geq 1$, and $b_{n-2}\geq 2$.

If it is true for $j=k$ and $j=k+1$, then let $i=(n-k)$. So, $b_{n-(k+2)} = b_{i-2}$. $b_{n-(k+1)} = b_{i-1}$. $b_{n-k} = b_i$. Then we see that $\min(b_{n-(k+2)}) = \min(b_{i-2}) \geq \min(b_{i-1})+ \min(b_{i}) = F_{k+1}+F_{k} = F_k$.

So, $b_{n-(k+2)} \geq F_{k+2}$, and the statement is thus true for $j=k+2$.

By mathematical induction then, we have that the statement is true for all integer $j$.

So, what have we proven so far?

Well, we have proven that $b_{n-n} = b \geq F_n$. In other words, the Knuth form of the theorem.

Now, how about the original?

Well, we just need to give the proof that each decimal place increase for the Fibonacci sequence takes at most 5 steps.

So.

Let us do that.

\begin{align} F_{n+5} & = f_{n+4}+f_{n+3}\\ & = f_{n+3} + f_{n+2} + f_{n+3}\\ & = 2f_{n+3}+f_{n+2}\\ & = 2f_{n+2}+2f_{n+1}+f_{n+2}\\ & = 3f_{n+2}+2f_{n+1}\\ & = 5f_{n+1}+3f_n\\ & = 8f_n+5f_{n-1}\\ & = 13f_{n-1}+8f_{n-2}\\ & = 10f_{n-1}+3f_{n-1}+8f_{n-2}\\ & = 10f_{n-1}+11f_{n-2}+3f{n-1}\\ & >10f_n \end{align}

So we have what we wanted. $F_n > 10 F_{n-5}$. So, we start with b. After 5 steps of the algorithm, $b$ has one less decimal places. If b has d decimal places, then after $5(d-1)$ steps, b only has 1 decimal place.

Hence, we are done.

I would like to note that the definition of the first step here might be slightly different, so the answer might be off by 1.

But in general, this is how you would do it.

Again, the best way to understand a proof is to replicate it via free recall.

$\endgroup$
  • $\begingroup$ Beautifully explained! Love the enthusiasm! :D $\endgroup$ – zerosofthezeta Jul 25 '13 at 23:43
  • $\begingroup$ @zerosofthezeta it works for natural numbers and also for integers ? $\endgroup$ – Maman Dec 5 '15 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.