Mathematical induction: What is it, what’s used for, and how to apply it.

Welcome to mathematics out of high school. We are not just asked to provide the right answer anymore but we are asked to prove why our answer is right. If you find yourself a little bit lost in this new universe of mathematics join me today in deciphering the mysteries behind this mathematic tool of precision.

Photo by Tom Wilson on Unsplash

There are many techniques to prove various statements. The simplest ones are direct proof, where you show that if the first statement (P) is true then the second statement (Q) is also true, and proof by contrapositive, where you assume that the negation of the second statement (~Q) is true and show that this forces the negation of the first statement (~P) to be true as well. Great, but today I am not here to talk about the very basics of the proofs (although I will attempt to reference important basic concepts along the article), I am here today to talk about mathematical induction which is a technique used to prove that an all statements of an infinite list of statements (instead of just two like in the first two techniques mentioned) are all true.

You might be wondering why I chose a picture of falling dominoes as the article’s cover. Well, I chose it because it illustrates the main idea behind induction. Let’s say we have a list of statements S_1, S_2, … , S_k and we want to show that all of those statements are true. For this, think of the statements as dominoes, can you think of a popular property of dominoes that might help us prove one statement is true and then all the following statements to be true as well? I’ll help you out. Take the first statement S_1 for example, this could be a common conditional (if…else) statement thus we could leverage any of the techniques mentioned in the first paragraph. Let’s assume we proved it. Now, we need to show that S_1 being true forces S_2 to be true, then that S_2 being true forces S_3 to be true, etc. You get the idea? In general, we must show that if any given statement S_k is true, then the following statement S_k+1 is also true. Just like dominoes! If one falls then all the following dominoes fall. I often find pictures very helpful at visualizing concepts like this so here you go:

source: Book of Proof, Richard Hammack

Hopefully that idea helped you start developing an intuition behind induction. But, just like everything in mathematics, we need to be rigorous and precise. Hence, here is the formal outline of mathematical induction:

Proposition: The statements S_1, S_2, S_3, S_4, … are all true.

1. Set up a basis step, which consists of the very first statement in your list, and prove it. In other words, prove that S_1 is true.
2. Set up an inductive step, which consists of choosing an arbitrary statement S_k and showing that if it is true then S_k+1 is also true. Direct proof is the technique used the most often in this step.

The assumption that S_k is true is called inductive hypothesis.

Pretty straightforward, right? Let’s apply this technique on a real problem now. I find it challenging to write in math notation on Medium so bare with me, I will do my best to keep it as clean as possible. Here we go:

Proposition: if n ∈ ℕ, then 1+3+5+7+…+(2n-1) = n².

Proof.

Note: We want to prove that the given statement is true for every n ∈ ℕ.

First we set up our basis step. Observe that the first statement is when n = 1. thus, if n =1 then 1 = 1², which is obviously true.

Next we set up our inductive step. For this, show that S_k → S_k+1 for some k ≥ 1. So, what does this mean? Well, we must show that if the statement 1+3+5+7+…+(2k-1) = k² (this is our S_k) is true, then the following statement 1+3+5+7+…+(2(k+1)-1) = (k+1)² is also true. We use direct proof to show this. Suppose 1+3+5+7+…+(2k-1) = k². Then

1+3+5+7+………..…….+(2(k+1)-1) =

1+3+5+7+…….+(2k-1)+(2(k+1)-1) =

( 1+3+5+7+…+(2k-1) )+(2(k+1)-1) =

k² + (2(k+1)-1) = k² + 2k + 1 = (k+1)² → which is what we want.

Thus, 1+3+5+7+…+(2(k+1)-1) = (k+1)², which proves S_k → S_k+1. Therefore, 1+3+5+7+…+(2n-1) = n² for every n ∈ ℕ.

Here is another problem if you want a little bit more practice. I’ll let you figure it out on your own.

Proposition: If n ∈ ℕ, then (1 + x)^n ≥ 1 + nx for all x ∈ ℝ with x > -1.

The technique we just learnt could be seen as a standard induction. In addition, there is a variant called strong induction that is used to prove the exact same type of problems as with “normal” induction but when it is particularly challenging to show that S_k → S_k+1 (or not possible at all). Strong induction gives us the possibility to use a “lower” statement as a reference to show that S_k+1 is true. In other words, instead of using the statement S_k, I could instead use a statement S_m, where m < k, to prove the conditional statement. The underlying idea behind strong induction is the same as with “normal” induction with the only difference that in the inductive step we assume that all the statements S_1, S_2, …, S_k are true (instead of assuming that only S_k is true) and show this forces S_k+1 to be true. To formalize this idea, here is the outline for strong induction:

Proposition: The statements S_1, S_2, S_3, S_4, … are all true.

1. Basis step: Prove the first statement S_1 (or the first several S_n).
2. Inductive step: Given any integer k ≥ 1, prove the following statement: (S_1 ∧ S_2 ∧ ··· ∧ S_k) → S_k+1.

Cool, let’s try out a problem to test our understanding:

Proposition: Any postage of 8¢ or more is possible using 3¢ and 5¢ stamps.

Basis step: This holds for postages of 8, 9 and 10 cents: For 8¢, use one 3¢ stamp and one 5¢ stamp. For 9¢, three 3¢ stamps. For 10¢, two 5¢ stamps.

Inductive step: Let k ≥ 10, and for each 8 ≤ m ≤ k, assume a postage of m cents can be obtained exactly with 3¢ and 5¢ stamps. (That is, assume statements S_8,S_9,…,S_k are all true.) We must show that S_k+1 is true, that is, (k+1)- cents postage can be achieved with 3¢ and 5¢ stamps. By assumption, S_k−2 is true. Thus we can get (k−2)-cents postage with 3¢ and 5¢ stamps. Now just add one more 3¢ stamp, and we have (k −2)+3 = k +1 cents postage with 3¢ and 5¢ stamps.

Finally, there is a third technique called proof by smallest counterexample which is like a combination of induction and contradiction. For those who don’t know — or might need a refresher — proof by contradiction consists of assuming that the negation of the statement is true and showing that such an assumption leads to a clear contradiction (something that makes no sense like 1 ≠ 1). Very well, the outline for proof by smallest counterexample is as follows:

Proposition: The statements S_1, S_2, S_3, S_4, … are all true.

1. Check that the first statement S_1 is true.
2. For the sake of contradiction, suppose not every S_n is true.
3. Let k > 1 be the smallest integer for which S_k is false.
4. Then S_k−1 is true and S_k is false. Use this to get a contradiction.

Let’s get our hands dirty.

Proposition: If n ∈ N, then 4 | (5^n −1).

Note: we are being asked to prove that the given statement is true for every natural number. Also, recall that the definition of divisibility states that an integer, a, divides another one, b, if b = a*c for some c ∈ ℤ.

The first natural number is 1. Thus, our first statement is n = 1. Then, our statement becomes 4 | (5¹ −1) and so 4 | 4, which is obviously true. Next, for the sake of contradiction suppose 4 | (5^n −1) is not true for all n. Moreover, let k > 1 be the smallest integer for which 4 ∤ (5^k −1). Then, the statement 4 |(5^(k-1) −1) is true. Hence, it follows by the definition that there must be an integer c such that (5^(k-1) −1) = 4c. Note that

(5^(k-1) −1) = 4c

5⋅(5^(k-1) −1) = 5 ⋅ 4c → to increment the exponent

5^k - 5 = 20c

5^k - 1 = 20c - 4 → remember our goal is to show 4 ∤ (5^k −1) is false.

5^k - 1 = 4(5c - 1)

Therefore, by definition, 4 | (5^k - 1) which contradicts our assumption that 4 ∤ (5^k −1). Thus, 4 | (5^n −1) for every n ∈ ℕ.

This concludes my short post on mathematical induction.

I hope you found it useful and informative. I mostly use writing as a complement to my studies because it helps me gain a much deeper understanding of the topics by writing down my thoughts as clear as possible so that anyone could understand.

If you have any suggestions or any feedback whatsoever definitely leave a comment.

Some other articles I wrote you might find interesting:

Topics in quant GRE: Data, Probability and Statistics

Topics in quant GRE: Number Properties

My adventure in Deep Learning — part 3.5