I mentioned that the naive way of computing the gcd of $m$ and $n$ was inefficient. This is because if the size of $n$ is $d = \log n$, then searching for divisors from 1 through $\sqrt n$ would require approximately $\sqrt n = 10^{\log \sqrt n} = 10^d$ steps, assuming your number was in decimal representation (swap with the appropriate base if desired). In other words, the number of steps we need to compute this grows exponentially as we increase the size of our number.
But does Euclid's algorithm do any better than this? How would we know? We'll take a brief excursion into algorithm analysis and learn about strong induction and some properties of the Fibonacci numbers along the way.
We will define this famous sequence of numbers in this way.
The Fibonacci numbers are defined by
This sequence is due to Fibonacci, an Italian mathematician from the 13th Century in what was then the Republic of Pisa. The Fibonacci numbers are one of those things from math that spookily shows up in all sorts of different places not only in mathematics, but in all sorts of natural phenomena. You may have been asked to compute the Fibonacci numbers as a programming exercise before.
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)Since this definition is recursive, the Fibonacci numbers seem to lend themselves to inductive proofs quite naturally. However, there is one snag with the definition of the Fibonacci numbers, and it's that they're defined in terms of the previous two terms. If we think back to our template, this means that we have to make a stronger assumption: if, for some statement $P$, we want to show $P(k+1)$, not only do we need to assume $P(k)$, but $P(k-1)$ as well.
This is where we need to introduce the notion of strong induction. Strong induction is a reformulation of our induction axiom that gives us a "stronger" hypothesis. Recall that we had \[P(0) \wedge \forall k \in \mathbb N, (P(k) \rightarrow P(k+1)) \rightarrow \forall n \in \mathbb N, P(n).\] Now, we have strengthened our hypothesis by adding an additional term: \[P(0) \wedge \forall k \in \mathbb N, (P(k-1) \wedge P(k) \rightarrow P(k+1)) \rightarrow \forall n \in \mathbb N, P(n).\] But what if we needed more terms? That's no problem either. \[P(0) \wedge \forall k \in \mathbb N, ((P(0) \wedge P(1) \wedge \cdots \wedge P(k-1) \wedge P(k)) \rightarrow P(k+1)) \rightarrow \forall n \in \mathbb N, P(n).\] Why does this work? One of the things you can try to convince yourself of is that this is actually no different from ordinary induction. It's not hard to see that every proof by induction is also a proof by strong induction, but it takes a bit more reasoning to convince ourselves of the converse.
Of course, if we think back to our computations on recursive definitons and functions, we remember that we saw a pattern: the computation for $f(n)$ always contained the computation for $f(n-1)$, which contained the computation for $f(n-2)$, which ...
So in fact, all strong induction does is make explicit a fact that was implicit: if $P(k-1)$ was true, it would necessarily have been the case that $P(k-2)$ was true, and so on. And since we proved that $P(0)$ was true right at the start, we can assume that everything from $P(0)$ to $P(k)$ is true if we assume that $P(k)$ is true.
This means we need to make a slight modification to our template for proof by induction in order to get a template for a proof by strong induction, namely: the inductive hypothesis.
Returning to Fibonacci numbers, sometimes we just want a nice neat formula to compute a term of a sequence like $f_n$, rather than having to compute every single term up to the $n$th one. We'll be showing how we can do this much later in the course, when we talk about recurrences. For now, we'll just say that one can get an exact formula for $f_n$ in terms of the solutions to the polynomial equation $x^2 - x - 1 = 0$. These are $\varphi = \frac{1 + \sqrt 5}{2}$, the Golden Ratio, and its conjugate root, $\widetilde \varphi = 1 - \varphi = \frac{1-\sqrt 5}{2}$. What we get is $$f_n = \frac{\varphi^n - \widetilde \varphi^n}{\sqrt 5}.$$ This is now known as Binet's formula, although it seems like it was known by a bunch of mathematicians like Euler, Bernoulli, and de Moivre over a century earlier.
For all $n \in \mathbb N$, $$f_n = \frac{\varphi^n - \widetilde \varphi^n}{\sqrt 5}.$$
We will show this by strong induction on $n$.
Base case. For $n = 0$, we have $f_0 = 0 = \frac{\varphi^0 - \widetilde \varphi^0}{\sqrt 5}$. For $n = 1$, we have \begin{align*} \frac{\varphi - \widetilde \varphi}{\sqrt 5} &= \frac{\frac{1+\sqrt 5}{2} - \frac{1-\sqrt 5}{2}}{\sqrt 5} \\ &= \frac{\frac{2\sqrt 5}{2}}{\sqrt 5} \\ &= \frac{\sqrt 5}{\sqrt 5} \\ &= 1 \end{align*}
Inductive case. Suppose that $f_j = \frac{\varphi^j - \widetilde \varphi^j}{\sqrt 5}$ for all $j$ with $j \leq k$. Consider $f_{k+1}$. \begin{align*} f_{k+1} &= f_k + f_{k-1} \\ &= \frac{\varphi^k - \widetilde \varphi^k}{\sqrt 5} + \frac{\varphi^{k-1} - \widetilde \varphi^{k-1}}{\sqrt 5} &\text{by ind. hyp.} \\ &= \frac{\varphi^k + \varphi^{k-1} - (\widetilde \varphi^k + \widetilde \varphi^{k-1})}{\sqrt 5} \\ &= \frac{(1 + \varphi) \varphi^{k-1} - (1 + \widetilde \varphi) \widetilde \varphi^{k-1}}{\sqrt 5} \\ &= \frac{\varphi^2 \varphi^{k-1} - \widetilde \varphi^2 \widetilde \varphi^{k-1}}{\sqrt 5} &\text{since $\varphi^2 = \varphi + 1$ and $\widetilde \varphi^2 = \widetilde \varphi+1$}\\ &= \frac{\varphi^{k+1} - \widetilde \varphi^{k+1}}{\sqrt 5} \end{align*}
Using this property of the Fibonacci numbers, we can prove something interesting about the Euclidean algorithm. The following is a result attributed to Gabriel Lamé in 1844, which makes it likely the earliest example of both analysis of an algorithm and an application of the Fibonacci numbers.
Suppose $a_n \gt a_{n-1} \gt \cdots \gt a_1 \gt a_0 = 0$ is the sequence of numbers obtained from Euclid's algorithm. Then $a_i \geq f_i$ for all $i \leq n$.
We will prove this by (strong) induction on $n$.
Base case. From the statement, we have $a_0 = f_0$ and $0 \lt a_1$ and $f_1 = 1 \leq a_1$.
Inductive case. Let $k \in \mathbb N$. Assume that $a_j \geq f_j$ for all $j \lt k$. Let $n = k+1$. By the Division Theorem, there exists an integer $q$ such that $a_{k+1} = q \cdot a_k + a_{k-1}$ and that $a_{k-1} \lt a_k$. Then $q \geq 1$ and \begin{align*} a_{k+1} &= q \cdot a_k + a_{k-1} \\ & \geq a_{k} + a_{k-1} \\ & \geq f_{k} + f_{k-1} & \text{by ind. hyp.} \\ & = f_{k+1} \end{align*}
Recall that when analyzing algorithms, we are concerned with the number of elementary operations that are performed in proportion to the size of the input and we are concerned with the growth of this function. Here, we consider the number of divisions to be our elementary operation, since that's the most important and costly operation we execute.
Let $a \gt b \geq 0$ be natural numbers such that the representation of $a$ requires $d$ decimal digits and the calculation of $\gcd(a,b)$ via Euclid's algorithm requires $k$ division steps. Then $k \leq 5 \cdot d$.
Since the decimal representation of $a$ requires $d$ digits, we have $a \lt 10^d$. If the computation of $\gcd(a,b)$ by Euclid's algorithm requires $k$ steps, by Lamé's Theorem, we have $a \geq f_k$. Then we have \begin{align*} f_k &\lt 10^d &\text{since $f_k \leq a \lt 10^d$}\\ \frac{\varphi^k}{\sqrt 5} &\leq 10^d &\text{since $f_k = \frac{\varphi^k - \widetilde \varphi^k}{\sqrt 5} \lt \frac{\varphi^k}{\sqrt 5}$}\\ k \log \varphi - \frac{\log 5}{2} &\leq d \log 10 &\text{apply $\log$ to both sides}\\ k &\leq \frac{d \log 10}{\log \varphi} - \frac{\log 5}{2 \log \varphi} &\text{isolate $k$}\\ k &\leq 4.789d + 1.673 \end{align*} That this implies $k \leq 5d$ is clear for large $d$. For small $d$, we can check the values by hand.
This is a neat result that goes back to our brief discussion about the efficiency of trying to find a gcd. What Lamé's theorem tells us is that Euclid's algorithm executes operations roughly linearly to the number of digits of the largest number $a$. The number of digits of a number turns out to be about $\log a$, so Euclid's algorithm scales roughly logarithmically with $a$.
If we compare this to the computing all the divisors method, we would be executing approximately as many operations as there are numbers from 1 to $n$. This means that our naive algorithm scales roughly linearly with $a$. Comparing the two algorithms, we have an approximately exponential difference between the two.