## Discussion and Examples

Induction is a means of proving a theorem by showing that if the theorem or assertion is true of any particular case, it is true of the next case in a series, and then showing it is indeed true in any particular case. Our text applies that definition to mathematics by saying mathematical induction is a technique for proving propositions over the positive integers. Mathematical induction reduces to a finite number of steps the proof that all positive integers belong to a specific truth set. The number of steps to complete the proof is the same, regardless of the size of the set or the number of positive integers involved. This is crucial to our discussion of discrete mathematics since it allows us to consider large volumes of evidence while deciding whether to accept or reject an assertion. As we develop automated systems or simply consider what we are hearing on the evening news, we find ourselves having to do exactly that.

### 3.4 Mathematical Induction

The structure of the natural numbers – 0, 1, 2, 3, and on to infinity – makes possible a powerful proof technique known as induction or mathematical induction. Although the idea behind induction is simple, students often struggle with it. Take your time and study this material thoroughly! You will have the opportunity to practice in the labs after we discuss induction in the lectures.

Let P be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that we can prove that P(0) is true. Suppose that we can also prove the statements P(0) P(1), P(1) P(2), P(2) P(3), and so on. The principle of mathematical induction is the observation that we can then conclude that P(n) is true for all natural numbers n. This should be clear. It's like a line of dominos, lined up and ready to fall, one after the next. Since P(0) and P(0) P(1) are true, we can apply the rule of modus ponens to conclude that P(1) is true. Then, since P(1) and P(1) P(2) are true, we can conclude by modus ponens that P(2) is true. From P(2) and P(2) P(3), we conclude that P(3) is true. For any given n in the set ℕ, we can continue this chain of deduction for n steps to prove that P(n) is true.

When applying induction, we don't actually prove each of the implications P(0) P(1), P(1) P(2), and so on, individually. That would require an infinite amount of work. The whole point of induction is to avoid any infinitely long process. Instead, we prove ∀k (P(k) P(k + 1)) (where the domain of discourse for the predicate P is ℕ. The statement ∀k(P(k) P(k + 1)) summarizes all the infinitely many implications in a single statement. Stated formally, the principle of mathematical induction says that if we can prove the statement P(0) ∧ (∀k(P(k) P(k + 1)), then we can deduce that ∀nP(n) (again, with ℕ as the domain of discourse).

#### 3.4.1 How to write a proof by induction

It should be intuitively clear that the principle of induction is valid. It follows from the fact that the list 0, 1, 2, 3, …, if extended long enough, will eventually include any given natural number. If we start from P(0) and take enough steps of the form P(k) P(k + 1), we can get P(n) for any given natural number n. However, whenever we deal with infinity, we are courting the possibility of paradox. We will prove the principle of induction rigorously in the next chapter (see Theorem 4.3), but for now we just state it as a theorem:

Theorem 3.4. Let P be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that P(0) ∧ (∀∈ ℕ (P(k) → P(k + 1))).4Then P(n) is true for all natural numbers n. (That is, the statement n P(n) is true, where the domain of discourse for P is the set of natural numbers.)

Mathematical induction can be applied in many situations: you can prove things about strings of characters by doing induction on the length of the string, things about graphs by doing induction on the number of nodes in the graph, things about grammars by doing induction on the number of productions in the grammar, and so on. We'll be looking at applications of induction for the rest of this chapter, and treat a form called structural induction in the next chapter.

Although proofs by induction can be very different from one another, they all follow just a few basic structures. A proof based on the preceding theorem always has two parts. First, P(0) is proved. This is called the base case of the induction. Then the statement ∀k (P(k) P(k + 1)) is proved. This statement can be proved by letting k be an arbitrary element of ℕ and proving P(k) P(k + 1). This in turn can be proved by assuming that P(k) is true and proving that the truth of P(k + 1) follows from that assumption. This case is called the inductive case, and P(k) is called the inductive hypothesis or the induction hypothesis. Note that the base case is just as important as the inductive case. By itself, the truth of the statement ∀k (P(k) P(k + 1)) says nothing at all about the truth of any of the individual statements P(n). The chain of implications P(0) P(1), P(1) P(2), …, P(n 1) P(n) says nothing about P(n) unless the chain is anchored at the other end by the truth of P(0).

#### 3.4.2 Examples

Let's look at a few examples.

Theorem 3.5. The number 221 is divisible by 3 for all natural numbers n.

Proof. Here, P(n) is the statement that 221 is divisible by 3.

Base case: When n = 0, 221 = 21 = 1 1 = 0 and 0 is divisible by 3 (since 0 = 3 · 0.) Therefore the statement holds when n = 0.

Inductive case: We want to show that if the statement is true for n = k (where k is an arbitrary natural number), then it is true for n = k + 1 also. That is, we must prove the implication P(k) P(k + 1). So we assume P(k), that is, we assume that 22is divisible by 3. This means that 221 = 3m for some integer m. We want to prove P(k + 1), that is, that 22(+ 1) 1 is also divisible by 3:

\begin{align*} 2^{2(k+1)}-1 &= 2^{2k+2} -1 \\ &= 2^{2k} \cdot 2^2 - 1 \; \; \; \; \; \; \; \;\; \; \; \; \; \; \; \; \mathrm{properties \; of \; exponents}\\ &= 4 \cdot 2^{2k} - 1\\ &= 4 \cdot 2^{2k} -4 +4 -1)\\ &= 4(2^{2k} -1) + 3 \; \; \; \; \; \; \; \; \; \; \; \mathrm{algebra}\\ &= 4(3m) + 3 \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \mathrm{inductive \; hypothesis}\\ &= 3(4m + 1) \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \mathrm{algebra} \end{align*}

and from the last line we see that 22+ 1 is in fact divisible by 3. (The third step – subtracting and adding 4 – was done to enable us to use our inductive hypothesis.)

Altogether, we have proved that P(0) holds and that, for all k, P(k) P(k + 1) is true. Therefore, by the principle of induction, P(n) is true for all n in ℕ, i.e. 2 2n1 is divisible by 3 for all n in ℕ.

The principle of mathematical induction gives a method for proving P(n) for all n in the set ℕ. It should be clear that if M is any natural number, a similar method can be used to show that P(n) is true for all natural numbers n that satisfy n ≥ M. Just start the induction with a base case of n = M instead of with a base case of n = 0. I leave the proof of this extension of the principle of induction as an exercise. We can use the extended principle of induction to prove a result that was first mentioned in Section 2.1.

Theorem 3.6. Suppose that a compound proposition contains exactly n propositional variables, where n ≥ 1. Then there are exactly 2different ways of assigning truth values to the n variables.

Proof. Let P(n) be the statement "There are exactly 2different ways of assigning truth values to n propositional variables". We will use induction to prove the P(n) is true for all n ≥ 1.

Base case: First, we prove the statement P(1). If there is exactly one variable, then there are exactly two ways of assigning a truth value to that variable. Namely, the variable can be either true or false. Since 2 = 21, P(1) is true.

Inductive case: Suppose that P(k) is already known to be true. We want to prove that, under this assumption, P(k + 1) is also true. Suppose that p1, p2, …, p+ 1 are k + 1 propositional variables. Since we are assuming that P(k) is true, we know that there are 2ways of assigning truth values to p1, p2, …, pk. But each assignment of truth values to p1, p2 , …, pcan be extended to the complete list p1, p2, …, pk, p+ 1 in two ways. Namely, p+ 1 can be assigned the value true or the value false. It follows that there are 2 · 2ways of assigning truth values to p1, p2, …, p+ 1. Since 2 · 2= 2+ 1, this finishes the proof.

#### 3.4.3 More examples

The sum of an arbitrary number of terms is written using the symbol ∑. (This symbol is the Greek letter sigma, which is equivalent to the Latin letter S and stands for 'sum'.) Thus, we have

$\sum_{i=1}^5 i^2 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2$

$\sum_{k=3}^7 a_k = a_3 + a_4 + a_5 + a_6 + a_7$

$\sum_{n=0}^N \frac{1}{n+1} = \frac{1}{0+1} + \frac{1}{1+1} + \frac{1}{2+1} + ... + \frac{1}{N+1}$

This notation for a sum, using the ∑ operator, is called summation notation. A similar notation for products uses the symbol ∏. (This is the Greek letter pi, which is equivalent to the Latin letter P and stands for 'product'.) For example,

$\prod_{k=2}^5 (3k+2) = (3 \cdot 2 + 2)(3 \cdot 3 +2)(3 \cdot 4 +2)(3 \cdot 5 +2)$

$\prod_{i=1}^n \frac{1}{i} = \frac{1}{1} \cdot \frac{1}{2} \cdot ... \cdot \frac{1}{n}$

Induction can be used to prove many formulas that use these notations. Here are two examples:

Theorem 3.7. $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ fo r any integer n greater than zero.

We'll prove this theorem. Can you do it yourself?

The summation of Theorem 3.7 is often attributed to mathematician and physicist Carl Friedrich Gauss (1777–1855). Gauss has been exceptionally influential in a variety of fields; he is called "the greatest mathematician since antiquity". For example, you might have heard of the Gaussian probability distribution, or perhaps of the Gauss unit for magnetic flux (although we now commonly use the Tesla for that, with 1 Tesla equalling 105 Gauss). His brilliance was already apparent in primary school when he allegedly used the 'Gauss sum' from Theorem 3.7 to solve the maths homework the teacher had set the class – to great astonishment of the teacher. You will see this summation again in the course Algorithms & Data Structures when analysing the runtime of algorithms containing loops.

Theorem 3.8. $\sum_{i=1}^n i2^{i-1} = (n-1) \cdot 2^n +1$ for any natural number n > 0.

Proof. Let P(n) be the statement $\sum_{i=1}^n i2^{i-1} = (n-1) \cdot 2^n +1$.  We use induction to show that P(n ) is true for all n > 0

Base case: Consider the case n = 1. P(1) is the statement that $\sum_{i=1}^n i2^{i-1} = (1-1) \cdot 2^1 + 1$ . Since each side of this equation is equal to one, this is true.

Inductive case: Let k > 1 be arbitrary, and assume that P(k) is true. We want to show that P(k + 1) is true. P(k + 1) is the statement $\sum_{i=1}^n i2^{i-1} = (n-1) \cdot 2^n + 1$. But, we can compute that

\begin{align*} \sum_{i=1}^{k+1} &= (\sum_{i=1}^k i2^{i-1}) + (k+1)2^{(k+1)-1}\\ &= ((k-1) \cdot 2^k + 1) + (k+1)2^k \; \; \; \; \mathrm{(inductive \; hypothesis)}\\ &= ((k-1) + (k+1))2^k + 1 \\ &= (k \cdot 2) \cdot 2^k + 1\\ &= k2^{k+1} +1 \end{align*}

which is what we wanted to show. This completes the induction.

For example, these theorems show that $\sum_{i=1}^{100} i = 1+2+3+4+ ... + 100 = \frac{100(100+1)}{2} = 5050$ and that 1 · 20 + 2 · 21 + 3 · 22 + 4 · 23 + 5 · 24 = (5 1)25 + 1 = 129, as well as infinitely many other such sums.

### 3.7 Mathematical Induction

#### 3.7.1 Introduction, First Example

In this section, we will examine mathematical induction, a technique for proving propositions over the positive integers. Mathematical induction reduces the proof that all of the positive integers belong to a truth set to a finite number of steps.

Example 3.7.1: Formula for Triangular Numbers. Consider the following proposition over the positive integers, which we will label p(n): The sum of the positive integers from 1 to n is $\frac{n(n+1)}{2}$. This is a well-known formula that is quite simple to verify for a given value of n. For example, p(5) is: The sum of the positive integers from 1 to 5 is $\frac{5(5+1))}{2}$. Indeed, 1 + 2 + 3 + 4 + 5 = 15 = $\frac{5(5+1)}{2}$. However, this doesn't serve as a proof that p(n) is a tautology. All that we've established is that 5 is in the truth set of p. Since the positive integers are infinite, we certainly can't use this approach to prove the formula.

An Analogy: A proof by mathematical induction is similar to knocking over a row of closely spaced dominos that are standing on end. To knock over the dominos in Figure 3.7.2, all you need to do is push the first domino over. To be assured that they all will be knocked over, some work must be done ahead of time. The dominos must be positioned so that if any domino is pushed is knocked over, it will push the next domino in the line. Figure 3.7.2 An analogy for Mathematical Induction, Creative Commons photo by Ranveig Thattai

Returning to Example 3.7.1 imagine the propositions p(1), p(2), p(3), . . . to be an infinite line of dominos. Let's see if these propositions are in the same formation as the dominos were. First, we will focus on one specific point of the line: p(99) and p(100). We are not going to prove that either of these propositions is true, just that the truth of p(99) implies the truth of p(100). In terms of our analogy, if p(99) is knocked over, it will knock over p(100).

In proving p(99) p(100), we will use p(99) as our premise. We must prove: The sum of the positive integers from 1 to 100 is $\frac{100(100+1)}{2}$. We start by observing that the sum of the positive integers from 1 to 100 is (1 + 2 + · · · + 99) + 100. That is, the sum of the positive integers from 1 to 100 equals the sum of the first ninety-nine plus the final number, 100. We can now apply our premise, p(99), to the sum 1 + 2 + · · · + 99. After rearranging our numbers, we obtain the desired expression for 1 + 2 + · · · + 100:

\begin{align*} 1 + 2 + ... + 99 + 100 &= (1 + 2 + ... + 99) + 100\\ &= \frac{99 \cdot (99 + 1)}{2} + 100 \; \; \; \mathrm{by \; our \; assumption \; of \; p(99)} \\ &= \frac{99 \cdot 100}{2} + \frac{2 \cdot 100}{2}\\ &= \frac{100 \cdot 101}{2} \\ &= \frac{100 \cdot (100 + 1)}{2} \end{align*}

What we've just done is analogous to checking two dominos in a line and finding that they are properly positioned. Since we are dealing with an infinite line, we must check all pairs at once. This is accomplished by proving that  p(n) ⇒ p( n + 1) for all n ≥ 1:

\begin{align*} 1 + 2 + ... + n + (n + 1) &= (1 + 2 + ... + n) + (n + 1)\\ &= \frac{n \cdot (n + 1)}{2} + (n+1)\; \; \; \mathrm{by \; p(n)} \\ &= \frac{n(n+1)}{2} + \frac{2(n + 1)}{2}\\ &= \frac{(n + 1)(n + 2)}{2} \\ &= \frac{(n + 1)((n + 1) + 1)}{2} \end{align*}

They are all lined up! Now look at p(1): The sum of the positive integers from 1 to 1 is 1· (1+1) . Clearly, p(1) is true. This sets off a chain reaction. Since p(1) ⇒  p(2), p(2) is true. Since p(2) ⇒  p(3), p(3) is true; and so on.

Theorem 3.7.3: The Principle of Mathematical Induction. Let p(n) be a proposition over the positive integers. If

1. p(1) is true, and
2. for all n ≥ 1, p(n) ⇒ p(n + 1),

then p(n) is a tautology.

Note: The truth of p(1) is called the basis for the induction proof. The premise that p(n) is true in the second part is called the induction hypothesis. The proof that p(n) implies p(n + 1) is called the induction step of the proof. Despite our analogy, the basis is usually done first in an induction proof. However, order doesn't really matter.

#### 3.7.2 More Examples

Example 3.7.4: Generalized Detachment.Consider the implication over the positive integers.

p(n) : q→ q1, q→ q2, . . . , q− 1 qn, q⇒ qn

A proof that p(n) is a tautology follows. Basis: p(1) is qq1, q0 ⇒ q1. This is the logical law of detachment which we know is true. If you haven't done so yet, write out the truth table of ((q0→ q1 ) ∧ q0 ) → q1 to verify this step.

Induction: Assume that p(n) is true for some n ≥1. We want to prove that p(n + 1) must be true. That is:

q0q1, q→ q2, . . . , q− 1 qn, q→ q+ 1, q0q+ 1

Here is a direct proof of p(n + 1):

Table 3.7.5

 Step Proposition Justification 1 − (n + 1) q0 → q1, q1 → q2, . . . , qn − 1 → qn, q0 Premises n + 2 qn (1) − (n + 1), p(n) n + 3 qn→ qn + 1 Premise n + 4 qn+1 (n + 2), (n + 3), detachment

Example 3.7.6:
An example from Number Theory. For all n ≥ 1, n3 + 2n is a multiple of 3. An inductive proof follows:

Basis: 13 + 2(1) = 3 is a multiple of 3. The basis is almost always this easy!

Induction: Assume that n ≥ 1 and n3 + 2n is a multiple of 3. Consider (n + 1)3 + 2(n + 1). Is it a multiple of 3?

\begin{align*} (n+1)^3 + 2(n+1) &= n^3 + 3n^2 + 3n + 1 + (2n +2)\\ &= n^3 + 2n + 3n^2 + 3n + 3 \\ &= (n^3 + 2n) + 3(n^2 + n + 1) \end{align*}

Yes, (n + 1)3 + 2(n + 1) is the sum of two multiples of 3; therefore, it is also a multiple of 3.

Now we will discuss some of the variations of the principle of mathematical induction. The first simply allows for universes that are similar to P such as {2, 1, 0, 1, . . .} or {567, 8, . . .}.

Theorem 3.7.7: Principle of Mathematical Induction (Generalized).

If p(n) is a proposition over {k0 , k0 + 1, k0 + 2, . . .}, where kis any integer, then p(n) is a tautology if

1. p(k0) is true, and
2. for all n k0, p(n) ⇒ p(n + 1).

Example 3.7.8: A proof of the permutations formula. In Chapter 2, we stated that the number of different permutations of k elements taken from an n element set, P (n; k), can be computed with the formula n!. (n-k)! We can prove this statement by induction on n. For n ≥0, let q(n) be the proposition

$P(n;k) = \frac{n!}{(n-k)!}$ for all k, 0 k n.

Basis: q(0) states that P (0; 0) if is the number of ways that 0 elements can be selected from the empty set and arranged in order, then $P(0;0) = \frac{0!}{0!} = 1$. This is true. A general law in combinatorics is that there is exactly one way of doing nothing.

Induction: Assume that q(n) is true for some natural number n. It is left for us to prove that this assumption implies that q(n + 1) is true. Suppose that we have a set of cardinality n + 1 and want to select and arrange k of its elements. There are two cases to consider, the first of which is easy. If k = 0, then there is one way of selecting zero elements from the set; hence

$P(n + 1;0) = 1 = \frac{(n+1)!}{(n+1+0)!}$

and the formula works in this case.

The more challenging case is to verify the formula when k is positive and less than or equal to n + 1. Here we count the value of P (n + 1; k) by counting the number of ways that the first element in the arrangement can be filled and then counting the number of ways that the remaining k 1 elements can be filled in using the induction hypothesis.

There are n + 1 possible choices for the first element. Since that leaves elements to fill in the remaining k 1 positions, there are P (n; k 1) ways of completing the arrangement. By the rule of products,

\begin{align*} P(n+1;k) &= (n+1)P(n;k-1) \\ &= (n+1)\frac{n!}{(n-(k-1))!} \\ &= \frac{(n+1)n!}{(n-k+1)!} \\ &= \frac{(n+1)!}{((n+1)-k)!} \end{align*} This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.