This leads us to the notion of the existence of an Extended Euclidean algorithm. The EEA is an algorithm that computes the gcd of $m$ and $n$ and the coefficients $a$ and $b$ from Bézout's lemma. We can treat these coefficients as a certificate or sanity test that the gcd we computed was really correct without having recompute the entire thing later on. The EEA gives us a way to compute the gcd so that without doing a lot of extra work, $a$ and $b$ fall out almost for free.
How does it work? For two integers $x$ and $y$, we iteratively compute the following values:
using initial values
We then compute $q$ and $r$ by computing the following: \begin{align*} r &= a_i - q \cdot b_i \\ &= (a_{x,i} \cdot x + a_{y,i} \cdot y) - q \cdot (b_{x,i} \cdot x + b_{y,i} \cdot y) \\ &= (a_{x,i} - q \cdot b_{x,i}) \cdot x + (a_{y,i} - q \cdot b_{y,i}) \cdot y. \end{align*}
Once we have these values, we can set the next iteration by
Example 3.15. Repeating our computation from above, we set $x = 232$ and $y = 72$. The EEA gives us the following.
| $i$ | $a$ | $a_x$ | $a_y$ | $b$ | $b_x$ | $b_y$ |
|---|---|---|---|---|---|---|
| 1 | 232 | 1 | 0 | 72 | 0 | 1 |
| 2 | 72 | 0 | 1 | 16 | 1 | -3 |
| 3 | 16 | 1 | -3 | 8 | -4 | 13 |
| 4 | 8 | -4 | 13 | 0 | 9 | -29 |
From the final row of the table, we get $\gcd(232,72) = 8, a = -4, b = 13$. Put together, we check $8 = 232 \cdot (-4) + 72 \cdot 13$.
Now, we'll define a system of arithmetic on integers based around remainders. Many times, we want to do calculations based around multiples of certain numbers, like time. Modular arithmetic formalizes these notions. One of the things we'll see is that in certain cases, working in these structures gives us a notion of "division" that is well-defined. The system of modular arithmetic was first developed by Gauss.
Definition 4.1. Let $m$ be an integer. For integers $a$ and $b$, we say that $a$ is congruent to $b$ modulo $m$, written $a = b \pmod m$ or $a \equiv_m b$, if $m \mid (a-b)$. Equivalently, $a = b \pmod m$ if $a \mathop{\mathbf{mod}} m = b \mathop{\mathbf{mod}} m$.
Here, we need to be careful to distinguish the notion of equivalence $a \pmod m$ versus the function $a \mathop{\mathbf{mod}} m$.
Ultimately, we want to be able to talk about integers that are equivalent to each other. An easy example of this is when we think about integers modulo 10, since our entire number system is built around 10s. We can formally define what it means to be equivalent.
Definition 4.2. A relation $\sim$ is an equivalence relation if $\sim$ satisfies the following:
Equivalence relations are called as such because they capture relationships that are similar to equality. For instance, if I have two formulas $\varphi$ and $\neg \neg \varphi$, we can't say they're equal because they aren't: they contain different symbols and one is longer than the other. However, we can say that they're logically equivalent because they mean the same thing. One can define the notion of logical equivalence more formally and then show that it satisfies the conditions for equivalence relations.
Theorem 4.3. For $m \gt 0$, $\equiv_m$ is an equivalence relation.
Proof.
Using the notion of an equivalence relation, we can divide $\mathbb Z$ into sets that contain equivalent members. For instance, if we choose $m = 2$, then all even numbers are equivalent to each other ($0 \pmod 2)$ and all odd numbers are equivalent to each other $(1 \pmod 2)$. These sets are called equivalence classes.
Definition 4.4. For all $m \gt 0$ and $a \in \mathbb Z$, we define the equivalence class modulo $m$ of $a$ to be the set of integers $$[a]_m = \{b \in \mathbb Z \mid b \equiv_m a\}.$$
Typically, we refer to equivalence classes by the "obvious" name, which is the member of the class that is between 0 and $m-1$. This is called the canonical representative of the class. Of course, we should keep in mind that $[0] = [m] = [2m] = [-m]$ and such. But in addition to this, sometimes the $[]_m$ gets dropped for convenience's sake and we have to determine from context whether "2" means $2 \in \mathbb Z$ or $[2]_m$. Usually, this becomes clear with the usage of $\pmod m$ and we will try to make that explicit, but outside of this course, that's not always guaranteed.
Now, we'll define how to do arithmetic on these things.
Theorem 4.5. We define operations $+$ and $\cdot$ on the equivalence classes of $m$ by
All of this seems a bit obvious, but we should think about what we're really doing here. We've defined operations $+$ and $\cdot$ that look like our usual operations on the integers. However, observe that we're not adding and multiplying integers; we've defined a notion of adding and multiplying sets of integers.
Based solely on this, there is no reason that what we've defined is guaranteed to work. For instance, how do we know that when adding two sets in this way that we even get a set that makes sense at all? Of course, we have to prove this and it will turn out that our definitions of equivalence classes and addition and multiplication on those classes is such that everything works out intuitively almost without a second thought.
Proof. We have to show that for $a_1 \equiv a_2 \pmod m$ and $b_1 \equiv b_2 \pmod m$, we have $a_1 + b_1 \equiv a_2 + b_2 \pmod m$ and $a_1 \cdot b_1 \equiv a_2 \cdot b_2 \pmod m$.
First, by definition, we have that $m \mid (a_1 - a_2)$ and $m \mid (b_1 - b_2)$. Then we have $m \mid ((a_1 - a_2) + (b_1 - b_2))$. We can easily rearrange this to get $m \mid ((a_1 + b_1) - (a_2 + b_2))$ and therefore, $a_1 + b_1 \equiv a_2 + b_2 \pmod m$.
Next, consider $a_1 b_1 - a_2 b_2$. Since $m \mid (a_1 - a_2)$ and $m \mid (b_1 - b_2)$ there exist integers $k$ and $\ell$ such that $km = a_1 - a_2$ and $\ell m = b_1 - b_2$. Then, \begin{align*} a_1 b_1 - a_2 b_2 &= (a_2 + km) (b_2 + \ell m) - a_2 b_2 \\ &= a_2 b_2 + a_2 \ell m + b_2 k m + k \ell m^2 - a_2 b_2 \\ &= m(a_2 \ell + b_2 k + k \ell m) \end{align*} and therefore, $m \mid (a_1 b_1 - a_2 b_2)$ and $a_1 b_1 \equiv a_2 b_2 \pmod m$. $$\tag*{$\Box$}$$
Now, we can define our structure.
Definition 4.6. Let $\mathbb Z_m = \{[0]_m, [1]_m, \dots, [m-1]_m\}$. The integers mod $m$ is the set $\mathbb Z_m$, together with the binary operations $+$ and $\cdot$. The integers mod $m$ are denoted by $\mathbb Z/\equiv_m$ or simply as $\mathbb Z_m$.
Up to now, we have been working implicitly in the structure $\mathbb Z$, the integers. As I've briefly alluded to before, we're not only talking about the domain $\mathbb Z$ but also how we interpret operations like $+$ and $\cdot$. The integers mod $m$, $\mathbb Z_m$, is another structure, whose basic elements are the equivalence classes with respect to $\equiv_m$.
These kinds of structures—a set together with binary operations $+$ and $\cdot$ and identities for both operations—are called rings.
The notation $\mathbb Z/\equiv_m$ gives us a hint at what's happening. We took $\mathbb Z$ and partitioned it into equivalence classes by the relation $\equiv_m$. This idea of taking an algebraic structure and constructing another structure based on an equivalence relation is something that comes up a lot in algebra and is called a quotient structure, where quotient in the algebraic context just means equivalence class.
I mentioned earlier that one of the things that this structure allows us to do is, under certain conditions, "divide" things in the sense that there is an operation that we can perform on elements of our structure that reverse mulitplication. I say "divide" because the operation that we perform is not really division. It's more accurate to say that we'll be showing that multiplicative inverses exist.
First, we need the following notions.
Definition 4.7. Two integers $a$ and $b$ are relatively prime (or coprime) if $\gcd(a,b) = 1$.
Recall that a prime number is defined as the following.
Definition 4.8. An integer $p$ greater than 1 is called prime if the only positive divisors of $p$ are 1 and $p$. Otherwise, $p$ is called composite.
Example 4.9. Primes are obviously relatively prime to any number less than them, since they don't have any divisors except 1 and themselves. However, non-prime numbers (called composite numbers) can be relatively prime, even to each other. The numbers 10 and 21 are not prime, since $10 = 2 \cdot 5$ and $21 = 3 \cdot 7$. However, they are relatively prime, since $\operatorname{Div}(10) = \{\pm 1, \pm 2, \pm 5, \pm 10\}$ and $\operatorname{Div}(21) = \{\pm 1, \pm 3, \pm 7, \pm 21\}$.
Theorem 4.10. If integers $m \gt 0$ and $a$ are relatively prime, then $a$ has a multiplicative inverse mod $m$. That is, there exists an integer $b$ such that $a \cdot b = 1 \pmod m$.
Proof. By Theorem 5.2 (Bézout's lemma), there exist integers $n$ and $b$ such that $n \cdot m + b \cdot a = 1$. Then, \begin{align*} [1]_m &= [n \cdot m + b \cdot a]_m \\ &= [n]_m \cdot [m]_m + [b]_m \cdot [a]_m \\ &= [n]_m \cdot [0]_m + [b]_m \cdot [a]_m \\ &= [b]_m \cdot [a]_m \end{align*} $$\tag*{$\Box$}$$
Example 4.11. Consider $\mathbb Z_4$. There are four equivalence classes: $0,1,2,3$. Since 1 and 3 are coprime, they have inverses: $1^{-1} = 1$ (this is obvious) and $3^{-1} = 3$, which we get by observing that $3 \cdot 3 = 9 = 1 \pmod 4$. However, 2 has no inverse: \begin{align*} 2 \cdot 0 &= 0 &\pmod 4 \\ 2 \cdot 1 &= 2 &\pmod 4 \\ 2 \cdot 2 &= 4 = 0 &\pmod 4 \\ 2 \cdot 3 &= 6 = 2 &\pmod 4 \end{align*}
One might ask whether there is any integer $m$ for which $\mathbb Z_m$ has a multiplicative inverse for all non-zero elements. Our discussion about prime numbers gives us a hint.
Theorem 4.12. If $a$ and $m$ are relatively prime and $a \gt 1$, then the multiplicative inverse of $a$ modulo $m$ is unique.
Proof. By Theorem 4.10, since $a$ and $m$ are relatively prime, $a$ has a multiplicative inverse modulo $m$. Suppose that $b$ and $c$ are multiplicative inverses of $a$. Then, \begin{align*} b &= b \cdot 1 &\pmod m \\ &= b \cdot (c \cdot a) &\pmod m \\ &= b \cdot (a \cdot c) &\pmod m \\ &= (b \cdot a) \cdot c &\pmod m \\ &= 1 \cdot c &\pmod m \\ &= c &\pmod m \\ \end{align*} $$\tag*{$\Box$}$$
Corollary 4.13. If $p$ is prime and $a \neq 0 \pmod p$, then $a$ has a multiplicative inverse mod $p$.
This is easy to see since every integer $2, \dots, m-1$ aren't divisors of $p$ and therefore share no common divisors with $p$.
Definition 4.14. When it exists, we denote the multiplicative inverse of $a$ by $a^{-1}$.
Up until now, we've been working in $\mathbb Z$, where "division" "doesn't work". However, we've proved sufficient conditions to create structures where "division" does work in a sense, in that multiplicative inverses are guaranteed to exist for every element. This means that we can solve linear equations like $$6x = 144 \pmod{17}$$ using our usual algebraic techniques. In fact, assuming we were working with the same modulus, it's not hard to solve a system of equations in the usual way (you will be asked to do this on this week's problem set).
However, what if we throw an additional twist in there and were presented with a system of linear congruences with different moduli? Consider the following: \begin{align*} x &\equiv 2 &\pmod 3 \\ x &\equiv 3 &\pmod 5 \\ x &\equiv 2 &\pmod 7 \end{align*}
This problem, solving for $n$, was posed by the Chinese mathematician Sunzi from the third century AD. The following theorem is due to him.
Theorem 4.15 (Chinese Remainder Theorem). Consider integers $a_1, a_2, \dots, a_k$ and suppose that $m_1, m_2, \dots, m_k$ are $k$ pairwise positive coprime moduli. Then the system of equations \begin{align*} x & \equiv a_1 & \pmod{m_1} \\ x & \equiv a_2 & \pmod{m_2} \\ & \vdots \\ x & \equiv a_k & \pmod{m_k} \end{align*} has a unique solution modulo $m_1 \cdot m_2 \cdots m_k$.
Proof. Let $a_1, \dots, a_k$ be arbitrary integers and let $m_1, \dots, m_k$ be arbitrary positive integers with $\gcd(m_i, m_j) = 1$ for $1 \leq i \lt j \leq k$. Let $n = m_1 \cdot m_2 \cdots m_k$. For each $1 \leq i \leq k$, we define $n_i = \frac n {m_i}$. Here, we will rely on a claim that we have not proved yet:
Theorem 4.17. If $a$ and $b$ are relatively prime and $a$ and $c$ are relatively prime, then $a$ and $bc$ are relatively prime.
From this, we have that $m_i$ is relatively prime to $n_i$.
First, we will consider a solution $x_i$ to the simultaneous congruences \begin{align*} x_i & \equiv 0 & \pmod{m_1} \\ x_i & \equiv 0 & \pmod{m_2} \\ & \vdots \\ x_i & \equiv 0 & \pmod{m_{i-1}} \\ x_i & \equiv 1 & \pmod{m_i} \\ x_i & \equiv 0 & \pmod{m_{i+1}} \\ & \vdots \\ x_i & \equiv 0 & \pmod{m_k} \end{align*} In other words, we set $a_i = 1$ and $a_j = 0$ for $j \neq i$.
Let $b = n_i^{-1} \pmod{m_i}$. Since $n_i$ and $m_i$ are relatively prime, this inverse must exist. Now, consider $x_i = b \cdot n_i$. We claim $x_i$ is a solution to this simultaneous congruence.
Observe that $x_i = b \cdot n_i = n_i^{-1} \cdot n_i = 1 \pmod{m_i}$. Then, we recall that $m_j \mid n_i$ for $i \neq j$. Therefore, we have $m_j \mid b \cdot n_i = x_i$. In other words, $x_i = 0 \bmod m_j$.
To solve the original simultaneous congruences, we take each of the $x_i$'s and let $x = a_1 \cdot x_1 + \cdots + a_k \cdot x_k$. Then $x$ is a solution to the simultaneous congruence. To verify this we observe that for each $m_i$, we have \begin{align*} x &= a_1 \cdot x_1 + \cdots + a_k \cdot x_k & \pmod{m_i} \\ &= a_1 \cdot 0 + \cdots + a_{i-1} \cdot 0 + a_i \cdot 1 + a_{i+1} \cdot 0 + \cdots + a+k \cdot 0 & \pmod{m_i} \\ &= a_i & \pmod{m_i} \end{align*}
To see that our solution is unique, suppose we have two solutions $x_1$ and $x_2$. Then $x_1 - x_2 = 0 \pmod{m_i}$ for every $i$. We must have $m_i \mid (x_1 - x_2)$ for each $i$. Here, we will rely on another claim we have not proved yet:
Theorem 4.18. If $a$ and $b$ are relatively prime, and $a \mid n$ and $b \mid n$, then $ab \mid n$.
Since all of our $m_i$ are pairwise relatively prime, $n = m_1 \cdots m_k$ also divides $x_1 - x_2$. Therefore, we have $x_1 = x_2 \pmod n$. $\tag*{$\Box$}$
Example 4.16. Here is the problem of Sunzi stated again. \begin{align*} x &\equiv 2 &\pmod 3 \\ x &\equiv 3 &\pmod 5 \\ x &\equiv 2 &\pmod 7 \end{align*}
To solve this, we follow the proof of the Chinese Remainder Theorem and begin by computing each $n_i = \frac{m_i}{n}$. We have $$n_1 = 5 \cdot 7 = 35, \quad n_2 = 3 \cdot 7 = 21, \quad n_3 = 3 \cdot 5 = 15.$$ Next, we compute the inverses of the $n_i$'s. We have $$35^{-1} = 2^{-1} = 2 \pmod 3, \quad 21^{-1} = 1^{-1} = 1 \pmod 5, \quad 15^{-1} = 1^{-1} = 1 \pmod 7.$$
Finally, we compute $x = a_1 x_1 + a_2 x_2 + a_3 x_3 \pmod{105}$: \begin{align*} x &= 2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 &\pmod{105} \\ &= 140 + 63 + 30 &\pmod{105} \\ &= 233 & \pmod{105}\\ &= 23 & \pmod{105} \end{align*}
We made two unproven claims about relative primitivity in the proof of the Chinese Remainder Theorem. Both make use of the GCD characterization given by Bézout. We will prove them now.
Theorem 4.17. If $a$ and $b$ are relatively prime and $a$ and $c$ are relatively prime, then $a$ and $bc$ are relatively prime.
Proof. Let $d = \gcd(a,bc)$. Since $a$ and $b$ are relatively prime and $a$ and $c$ are relatively prime, we have \begin{align*} 1 &= am_1 + bn_1 \\ 1 &= am_2 + cn_2 \end{align*} for some integers $m_1, m_2, n_1, n_2$ by Bézout's lemma. Multiplying the two equations, we get \begin{align*} 1 &= a^2 m_1 m_2 + a c m_1 n_2 + a b m_2 n_1 + bcn_1 n_2 \\ &= a(a m_1 m_2 + c m_1 n_2 + b m_2 n_1) + bc (n_1 n_2). \end{align*} Let $m = a m_1 m_2 + c m_1 n_2 + b m_2 n_1$ and $n = n_1 n_2$, both of which are integers. Since $d = \gcd(a,b)$, we have that $d \mid (am + bcn)$. But this means that $d \mid 1$, so $\gcd(a,bc) = 1$. $\tag*{$\Box$}$
Theorem 4.18. If $a$ and $b$ are relatively prime, and $a \mid n$ and $b \mid n$, then $ab \mid n$.
Proof. Since $a \mid n$, there exists an integer $s$ such that $as = n$. Similarly, there exists an integer $t$ such that $bt = n$. Since $\gcd(a,b) = 1$, there exist integers $x,y$ such that $ax + by = 1$. We can write \begin{align*} n &= axn + byn \\ &= axbt + byas \\ &= ab(xt + ys) \end{align*} and therefore $ab \mid n$. $\tag*{$\Box$}$
We've already seen some examples of prime numbers behaving much nicer than ordinary numbers. For instance, recall that if we have $\mathbb Z_m$ and $m$ is prime, then every non-zero element in $\mathbb Z_m$ is guaranteed to have mulitiplicative inverses. This is because primes happen to be the building blocks for the integers. Mathematicians are particularly interested in objects that are atomic or can't be broken down any further or are minimal. The idea is that understanding the most basic, constituent objects gives us an understanding of the more complex structures they build. So the notion of primality is something that shows up in many more places than just number theory. We've already seen an example of this: atomic versus compound propositions in propositional logic.
In light of this, the following result is an extremely important one that we'll be working towards proving.
Theorem 6.1 (Fundamental Theorem of Arithmetic). Every natural number $n \gt 1$ can be written uniquely as a product of primes.
Before proving this, there is a lot of legwork we need to do. For instance, how do we prove something about all (or almost all) natural numbers? To do this, we need to make use of a new proof technique that exploits the structure of the natural numbers.
Definition 5.1. Let $\varphi(n)$ be a statement that depends on $n \in \mathbb N$. If
This is called the principle of mathematical induction.
How and when do we make use of this? Mathematical induction is a property of the natural numbers. What this means is that if there is some property that we want to prove about all natural numbers, all we need to do is prove that the property holds for the number 0 and that for any other natural number $k$, if it's true for $k$, then we can show that it's true for the next natural number, $k+1$.
More formally, to prove that for all $n \in \mathbb N$ that $\varphi(n)$ holds,
So why does this even work? Basically, what we're really proving is a very large, infinite chain of implications, \begin{align*} \varphi(0)&, \\ \varphi(0) &\rightarrow \varphi(1), \\ \varphi(1) &\rightarrow \varphi(2), \\ \varphi(2) &\rightarrow \varphi(3), \\ & \vdots \end{align*} The usual analogy for this is a chain of dominoes: we set up our argument so that any one domino is guaranteed to knock over the next domino ($\varphi(k) \rightarrow \varphi(k+1)$ for any $k$). Once we've set this up, all we need to do is knock over the first domino (showing $\varphi(0)$) to set off the chain reaction.
This leads us to what a proof by induction actually looks like.
Definition 5.2. For integers $n$ and $m$, we define the sum of $x_i$ for $i$ from $m$ to $n$ by $$\sum_{i = m}^n x_i = x_m + x_{m+1} + \cdots + x_{n-1} + x_n.$$
Theorem 5.3. For every $n \in \mathbb N$, $$\sum_{i=0}^n i = \frac{n(n+1)}2.$$
If you've been taught this formula before, then you've probably been told the story of Gauss solving this problem when he was 7. However, his teachers, in assigning $n = 100$, gave him an easy out since he only needed to consider one instance of the problem, so his solution does not use induction. We don't have that luxury, since we want to prove that this formula holds for all $n$.
Proof. We will prove this by induction on $n$.
Base case. $n = 0$. Then $$\sum_{i = 0}^0 i = 0 \quad \text{and} \quad \frac{0 \cdot (0+1)}2 = 0,$$ so clearly $\sum_{i=0}^n i = \frac{n(n+1)}2$ holds for $n=0$.
Inductive case. Let $k \in \mathbb N$ be arbitrary and assume that $\sum_{i=0}^k i = \frac{k(k+1)}2$. We will show that $\sum_{i=0}^{k+1} i = \frac{k+1(k+2)}2$. We have \begin{align*} \sum_{i=0}^{k+1} i &= \sum_{i=0}^k i + (k+1) \\ &= \frac{k(k+1)}2 + (k+1) & \text{by ind. hyp.} \\ &= (k+1) \cdot \left(\frac k 2 + 1 \right) \\ &= (k+1) \cdot \left(\frac k 2 + \frac 2 2 \right) \\ &= \frac{(k+1)(k+2)}2 \end{align*} Thus, we have shown that $\sum_{i=0}^n i = \frac{n(n+1)}2$ holds for $n=k+1$. Therefore, $\sum_{i=0}^n i = \frac{n(n+1)}2$ holds for all $n \in \mathbb N$. $\tag*{$\Box$}$
Recall the following theorem:
Theorem 2.8. If $A$ is a finite set, then $|\mathcal P(A)| = 2^{|A|}$.
Now, using induction, we can prove this.
Proof. We will prove this by induction on the size of $A$, $n = |A|$.
Base case. We have $|A| = 0$ and therefore, $A = \emptyset$. Then $\mathcal P(A) = \{\emptyset\}$. Observe that $|P(\emptyset)| = |\{\emptyset\}| = 1 = 2^0$.
Inductive case. Let $n = k$ and assume that if there is a set $|B|$ with $|B| = k$, then $|\mathcal P(B)| = 2^k$. Let $|A| = k+1$ and we will show that $|\mathcal P(A)| = 2^{k+1}$.
Choose an element $a \in A$. We define the set $A' = \{x \in A \mid x \neq a\}$ containing all elements of $A$ except $a$. Then $|A'| = |A| - 1$, since we removed $a$. Then $|A'| = k$ and by our inductive hypothesis, $|\mathcal P(A')| = 2^k$.
Now, consider a subset of $A'$, $X \in \mathcal P(A')$. For each subset $X \subseteq A'$, we can obtain two subsets of $A$, $X$ and $X \cup \{a\}$. Therefore, we have $2 \cdot 2^k = 2^{k+1}$ subsets of $A$. $\tag*{$\Box$}$
An observation that you may have made is that induction is a fine way to prove that something works, but it is not necessarily a great way to discover what it is you might want to prove. Other methods are necessary to come up with a hypothesis which you can then hopefully prove via induction.
Suppose we wish to determine a formula for the sum of the first $n$ consecutive odd numbers, $\sum_{i=0}^n (2i+1)$. We would have to try out a few values and see where we end up. \begin{align*} 1 &= 1 &i = 0\\ 1 + 3 &= 4 &i = 1\\ 1 + 3 + 5 &= 9 &i = 2\\ 1 + 3 + 5 + 7 &= 16 &i = 3\\ 1 + 3 + 5 + 7 + 9 &= 25 &i = 4\\ \end{align*} So it looks like a familiar pattern has developed, so we can attempt to prove it.
Theorem 5.4. For all $n \in \mathbb N$, $$\sum_{i=0}^n (2i+1) = (n+1)^2.$$
Proof. We will prove this by induction on $n$.
Base case. Let $n = 0$. Then $\sum_{i=0}^0 (2i+1) = 1 = 1^2$.
Inductive case. Let $k \in \mathbb N$ be arbitrary and assume that $\sum_{i=0}^k (2i-1) = (k+1)^2$. We want to show that $\sum_{i=0}^{k+1} (2i+1) = (k+2)^2$. We have \begin{align*} \sum_{i=0}^{k+1} (2i+1) &= \sum_{i=0}^{k} (2i+1) + 2(k+1) + 1 \\ &= (k+1)^2 + 2(k+1) + 1 &\text{ind. hyp.} \\ &= k^2 + 2k + 1 + 2k + 2 + 1 \\ &= k^2 + 4k + 4 \\ &= (k+2)^2 \end{align*} $\tag*{$\Box$}$
Now here we happened to end up with a recognizable pattern. But what happens if you don't? The snide answer is to Google it and that might work if you happen to be looking for a relatively famous sequence. However, Google isn't great if you just throw a bunch of numbers at it. So you might be expecting me to build up to show you how to do this "properly" but in my opinion, that's a lot of work and a bit outside the scope of the course.
Instead, I'd like to highlight the excellent Online Encyclopedia of Integer Sequences, founded by Neil Sloane. The OEIS is purpose-built to be a search engine for integer sequences and it contains more sequences than you can ever have imagined, complete with bibliographic links and other related sequences.
We can also use induction to prove inequalities. Something that we do in the analysis of algorithms is compare the growth rate of functions. We can use inductive arguments to do the same, since we often use functions with the domain $\mathbb N$ when quantifying computational resources like time or space.
Theorem 5.5. For all $n \in \mathbb N$ and $x \geq 0$, $(1+x)^n \geq 1+nx$.
Proof. We will show this by induction on $n$.
Base case. Let $n = 0$. Then $(1+x)^0 = 1 \geq 1 = 1 + 0 \cdot x$.
Inductive case. Let $k \in \mathbb N$ be arbitrary and assume that $(1+x)^k \geq 1+kx$. Consider $n = k+1$. \begin{align*} (1+x)^{k+1} &= (1+x)^k (1+x) \\ &\geq (1+kx) (1+x) & \text{ind. hyp.} \\ &= 1 + kx + x + kx^2 \\ &= 1 + (k+1)x + kx^2 \\ &\geq 1+(k+1)x & kx^2 \geq 0 \end{align*} $\tag*{$\Box$}$
Note that in this result, our functions had two variables, $x$ and $n$. This is a great example of why what you're applying induction to needs to be carefully considered and clearly stated.
If we have a result for some fixed integer, we can often generalize those arguments by using induction. For instance, in the proof of the Chinese Remainder Theorem, we relied on the claim that if $a$ and $b$ are relatively prime, and $a \mid n$ and $b \mid n$, then $ab \mid n$ to show that the product of all the moduli $m_i$ divided our solutions $x - x'$. In fact, the claim alone is insufficient to prove what we wanted to prove and we really needed to combine it with an inductive argument. For instance, consider the following generalization of De Morgan's laws.
Theorem 5.6. Let $p_1, p_2, \dots, p_n$ be propositional variables for $n \geq 1$. Then $$\neg \left( \bigwedge_{i=1}^n p_i \right) = \bigvee_{i=1}^n \neg p_i.$$
The big $\wedge$ and $\vee$ are analogs of the summation symbol $\sum$ in that we're taking the conjunction or disjunction of the indexed terms, similar to the big $\cup$ or $\cap$ which we defined earlier.
Proof. We will prove this by induction on $n$.
Base case. Let $n = 1$. Then $\neg \left( \bigwedge_{i=1}^1 p_i \right) = \neg p_1 = \bigvee_{i=1}^1 \neg p_i$.
Inductive case. Let $k \in \mathbb N$ be arbitrary and assume that $$\neg \left( \bigwedge_{i=1}^k p_i \right) = \bigvee_{i=1}^k \neg p_i.$$ Now, consider $n = k+1$. We have \begin{align*} \neg \left( \bigwedge_{i=1}^{k+1} p_i \right) &= \neg \left( \bigwedge_{i=1}^{k} p_i \wedge p_{k+1} \right) \\ &= \neg \left( \bigwedge_{i=1}^{k} p_i \right) \vee \neg p_{k+1} &\text{De Morgan's laws} \\ &= \bigvee_{i=1}^{k} \neg p_i \vee \neg p_{k+1} &\text{ind. hyp.} \\ &= \bigvee_{i=1}^{k+1} \neg p_i \\ \end{align*} $\tag*{$\Box$}$
Where induction really shines is when we work with recursively defined objects. For example, consider the definition of the factorial. Informally, we understand it to be $n! = 1 \cdot 2 \cdots n$, the product of the first $n$ consecutive integers. This definition is straightforward, but it doesn't really tell us much about the structure of the factorial and how we might decompose it if we wanted to prove something about it. The following is a more formal definition that helps in this regard.
Definition 5.7. The factorial $n!$ is defined inductively,
Here, we've split our definition up into a base case and an inductive case. We call these inductive or recursive definitions. These are particularly useful if we want to prove something about such objects using induction. We will define the following famous sequence of numbers in this way.
Definition 5.8. The Fibonacci numbers are defined by
In this form, the Fibonacci numbers 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 we want to show $\varphi(k+1)$, not only do we need to assume $\varphi(k)$, but $\varphi(k-1)$ as well.
Now, for only two terms, this isn't a huge issue and we've pretty much solved our problem already. But this is a nice place to introduce the notion of strong induction. Strong induction is a reformulation of induction that gives us a "stronger" hypothesis. In our case, we strengthened our hypothesis by adding an additional term. But what if we needed more, like every term that preceded $k+1$? This is where we deploy this proof method.
Definition 5.9. Let $\varphi(n)$ be a statement that depends on $n \in \mathbb N$. If
are both true, then the following is true:
This is called the principle of strong induction.
What is the difference between ordinary mathematical induction and strong induction? Or, in other words, what makes strong induction strong? The hypothesis that we make in each of our implications is stronger. Recall that ordinary induction was stated as a chain of implications $\varphi(k) \rightarrow \varphi(k+1)$. Strong induction is a chain of implications of the form $$\varphi(0) \wedge \varphi(1) \wedge \varphi(2) \wedge \cdots \wedge \varphi(k) \rightarrow \varphi(k+1).$$ Then what we're really proving is all of the following statements, \begin{align*} &\varphi(0), \\ \varphi(0) \rightarrow &\varphi(1), \\ \varphi(0) \wedge \varphi(1) \rightarrow &\varphi(2), \\ \varphi(0) \wedge \varphi(1) \wedge \varphi(2) \rightarrow &\varphi(3), \\ & \vdots \end{align*}
It's important to note that strong induction is not stronger in the sense that it allows us to prove things that we wouldn't be able to with mathematical induction. This is why I described strong induction as an alternate form of mathematical induction. It is possible to use mathematical induction to prove anything we would prove with strong induction, but this involves slightly altering the statement that you want to prove to incorporate your stronger assumptions.
A proof by strong induction looks similar to a proof by mathematical induction.
Returning to Fibonacci numbers, just like with sums, sometimes we just want a nice neat formula to compute one term $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 $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.
Theorem 5.10. For all $n \in \mathbb N$, $$f_n = \frac{\varphi^n - \widetilde \varphi^n}{\sqrt 5}.$$
Proof. 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*} $\tag*{$\Box$}$
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.
Theorem 5.11 (Lamé's Theorem). 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$.
Proof. 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. Assume that $a_j \geq f_j$ for all $j \lt n$. By the Division Theorem, there exists an integer $q$ such that $a_n = q \cdot a_{n-1} + a_{n-2}$ and that $a_{n-2} \lt a_{n-1}$. Then $q \geq 1$ and \begin{align*} a_n &= q \cdot a_{n-1} + a_{n-2} \\ & \geq a_{n-1} + a_{n-2} \\ & \geq f_{n-1} + f_{n-2} & \text{by ind. hyp.} \\ & = f_n \end{align*} $\tag*{$\Box$}$
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.
Corollary 5.12. 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$.
Proof. 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 \\ \frac{\varphi^k}{\sqrt 5} &\leq 10^d \\ k \log \varphi - \frac{\log 5}{2} &\leq d \log 10 \\ k &\leq \frac{d \log 10}{\log \varphi} - \frac{\log 5}{2 \log \varphi} \\ 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. $\tag*{$\Box$}$
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.