First Examples Using Mathematical Induction

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$.

Conclusion

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.