First Examples Using Mathematical Induction

by Dave

In this video, I’m going to cover three first examples using mathematical induction. So I’m going to assume that you have never seen mathematical induction before. So this is the first step, in a series of steps, to learn how to use and what mathematical induction is. Of course, to do that, we need to start with what the natural numbers are.

In the following, I use $\mathbb{N}$ to mean the set of natural numbers: $\{0,1,2,3, \ldots \}.$ In this first video, we are not going to say what we mean by $\ldots$. The important part of this video is to get a basic understanding of what mathematical induction is and to take those first steps by looking at some first examples using mathematical induction. So for this to happen, of course, we need the statement of mathematical induction.

Theorem. If $P$ is a subset of the natural numbers $\mathbb{N}$ with the following properties:

(1) $0 \in P$, and

(2) for all $k\in \mathbb{N}$, $k \in P$ implies $k+1 \in P$,

then $P$ is the set of natural numbers.

The statement in (1) is called the base case, and the hypothesis in statement (2) is called the induction hypothesis.

Here are the first examples using mathematical induction

This first example is by far the most common first example using mathematical induction.

Example 1. Prove that for all natural numbers $n$, $$\sum_{i=0}^n i =\frac{n(n+1)}{2}.$$

While working through the second example using mathematical induction, notice how example 1 and example 2 are very similar in their structure.

Example 2. Prove that for all natural numbers $n$, $$\sum_{i=0}^n i^2 =\frac{n(n+1)(2n+1)}{6}.$$

The first two examples are about summations. The third example is about an inequality.

Example 3. Prove that for all natural numbers $n$, $2^n > n$.


And there we have it, our very first three examples using mathematical induction. Of course, mathematical induction needs a lot more than these first examples to master it. In this course, induction plays a crucial role. So we will look at different types and various forms of mathematic induction, and we’re going to get a lot better.

To learn a great deal more on this topic, consider taking the online course The Natural Numbers.