CMSC 27100 — Lecture 8

How fast is Euclid’s algorithm?

We briefly mentioned that the naive way of computing the gcd of $m$ and $n$ is considered inefficient.

So 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 attributed to Fibonacci, an Italian mathematician from the 13th Century in what was then the Republic of Pisa, though their origin can be traced further back to a number of Indian mathematicians as early as the 3rd Century BC. 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: int) -> int:
    match n:
        case 0:
            return 0
        case 1:
            return 1
        case _:
            return fib(n-1) + fib(n-2)

Since this definition is recursive, the Fibonacci numbers seem to lend themselves to inductive proofs quite naturally. For instance, something we like to do with recursively defined sequences like this is to find a closed form for them. This would allow us to compute something like $f_{200}$ without having to compute $f_{2}$ through $f_{199}$ first.

It turns out that one can get an exact formula for $f_n$ in terms of the solutions to the polynomial equation $x^2 - x - 1 = 0$. There are a few ways to arrive here, none of which we’ll be going through. But the roots of this equation 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 natural numbers $n$, $$f_n = \frac{\varphi^n - \widetilde \varphi^n}{\sqrt 5}.$$

We will show this by induction on $n$.

Base case. For $n = 0$, we have $f_0 = 0$ by definition and $\frac{\varphi^0 - \widetilde \varphi^0}{\sqrt 5} = 0$. For $n = 1$, we have $f_1 = 1$ by definition and \[ \frac{\varphi^1 - \widetilde \varphi^1}{\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. \]

Inductive case. Let $k$ be an arbitrary natural number. Suppose that $f_k = \frac{\varphi^k - \widetilde \varphi^k}{\sqrt 5}$. Consider $f_{k+1}$. \begin{align*} f_{k+1} &= f_k + f_{k-1} & \text{Fibonacci numbers} \\ &= \frac{\varphi^k - \widetilde \varphi^k}{\sqrt 5} + f_{k-1} &\text{inductive hypothesis} \\ &\cdots \end{align*}

Unfortunately, it seems like we are stuck here. We need to say something about $f_{k-1}$ but our inductive hypothesis only covers $f_k$. What can we do?

Strong Induction

One way to fix this is to change the statement we’re trying to prove by including some additional information about terms that come before $n$. This is kind of awkward. What would be better if there were a way to add a bit more to our inductive hypothesis. However, the induction axiom doesn’t have any room for this: \[P(0) \wedge \forall k (P(k) \rightarrow P(k+1)) \rightarrow \forall n P(n).\]

The inductive hypothesis here is $P(k)$. If we want to say more in our inductive hypothesis, we have to change our axiom and replace $P(k)$ with something else. When we add more to our inductive hypothesis, we make our inductive hypothesis stronger, since we are assuming more. This leads to the following stronger induction axiom: \[P(0) \wedge \forall k (\forall j(j \leq k \rightarrow P(j)) \rightarrow P(k+1)) \rightarrow \forall n P(n).\] This is called strong induction since the assumption we make in the inductive case is stronger.

Let’s take a closer look at the hypothesis for the implication in the inductive case: \[\forall j(j \leq k \rightarrow P(j)).\] So what are we assuming? For every $j$, if $j \leq k$ then $P(j)$ is true. A more “natural” way of phrasing this might be “$P(j)$ for every $j \leq k$”. So where we used to write “Assume $P(k)$”, we’d now write something like “Assume $P(j)$ for all $j \leq k$”.

Sometimes, you may see strong induction be a bit less strong than this and instead specify the assumption a bit more modestly by enumerating a number of cases like \[P(0) \wedge \forall k (P(k-1) \wedge P(k) \rightarrow P(k+1)) \rightarrow \forall n P(n).\] This is also okay, but unnecessary, since strong induction covers this anyway.

But 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)$, and so on...

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.

  1. Prove the necessary base cases.
  2. Prove the inductive case.
    1. Choose an arbitrary natural number $k$.
    2. State your inductive hypothesis. Here, there are two broad kinds of inductive hypotheses that you can use for proof by strong induction
      1. Your inductive hypothesis would be to assume that $P(j)$ holds for all natural numbers $j$ with $0 \leq j \leq k$. This always works.
      2. If you have a constant number of steps back you want to consider, you may choose to assume that \[P(k-i+1) \wedge P(k-i+2) \wedge \cdots \wedge P(k-1) \wedge P(k).\] Here, $i$ is the number of terms you need. For example, in the case of the Fibonacci sequence, you will need $i = 2$, so you want to assume $P(k-1)$ and $P(k)$ hold. This assumes that $i$ is small enough that it makes sense to just list the terms.
    3. Use this assumption together with known facts to prove $P(k+1)$. You should clearly state when you use the inductive hypothesis.

Let’s go back to the proof of Binet’s formula.

We will show $f_n = \frac{\varphi^n - \widetilde \varphi^n}{\sqrt 5}$ by strong induction on $n$.

Base case. For $n = 0$, we have $f_0 = 0$ by definition and $\frac{\varphi^0 - \widetilde \varphi^0}{\sqrt 5} = 0$. For $n = 1$, we have $f_1 = 1$ by definition and \[ \frac{\varphi^1 - \widetilde \varphi^1}{\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. \]

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} & \text{Fibonacci numbers} \\ &= \frac{\varphi^k - \widetilde \varphi^k}{\sqrt 5} + \frac{\varphi^{k-1} - \widetilde \varphi^{k-1}}{\sqrt 5} &\text{inductive hypothesis} \\ &= \frac{\varphi^k + \varphi^{k-1} - (\widetilde \varphi^k + \widetilde \varphi^{k-1})}{\sqrt 5} & \text{grouping terms} \\ &= \frac{(1 + \varphi) \varphi^{k-1} - (1 + \widetilde \varphi) \widetilde \varphi^{k-1}}{\sqrt 5} & \text{factoring out $\varphi^{k-1}$ and $\widetilde \varphi^{k-1}$}\\ &= \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*}

Note that the identities used in the last line come from the fact that $\varphi$ and $\widetilde \varphi$ are the roots of $x^2 - x - 1 = 0$.

On Euclid’s algorithm

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 one of the earliest examples of an analysis of an algorithm (though there is slightly earlier work on the same subject) as well as a nice application of the Fibonacci numbers.

Typically, we represent the running time of an algorithm on inputs of size $n$ as a function $T(n)$. For iterative algorithms, we might use $T(n)$ to count the number of operations. For recursive algorithms, this typically means that $T(n)$ becomes recursively defined. Because of this, we often use $T(n)$ to count a particular operation instead of all of them.

For example, when thinking about binary search, the operation we care most about is integer comparison. In other words, how many integer comparisons do we need to make in order to determine whether we locate our item in the list? In an ordinary search, we may have to compare our item against every single item, while in binary search, we perform far fewer comparisons.

For Euclid’s algorithm, the operation of interest is division. On each recursive call, we must perform a division operation to acquire the remainder. The following theorem links the number of divisions performed by Euclid’s algorithm together with 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$.

Here, the sequence of integers $a_n, a_{n-1}, \dots, a_1, a_0$ is the sequence that we obtain via the following: \begin{align*} \gcd(a_n, a_{n-1}) &= \gcd(a_{n-1}, a_{n-2}) \\ &= \gcd(a_{n-2}, a_{n-3}) \\ & \vdots \\ &= \gcd(a_{2}, a_{1}) \\ &= \gcd(a_{1}, a_{0}) \end{align*}

So the setup here is that for $a$ and $b$ and without loss of generality, if $a \geq b$ so that $a_n = a$ and $a_{n-1} = b$, this sequence represents computing the $\gcd(a,b)$ via $n$ recursive calls. What Lamé’s theorem says is that this sequence grows at roughly the same pace as the Fibonacci numbers, which places a bound on the length of the sequence—the number of steps that are taken.