# Mathematical Induction Principles (Basis Step Required)

(D4M) — Here is the video transcript for this video.

What are mathematical induction principles? Wait no further, in this article we explain what they are.

The induction principle is analogous to an infinite string of dominos set up in a single line arranged so that if one falls down then so does the next one. Imagine you knock down the first domino, and then after some time has passed you check back and the dominos are still falling. Would you believe that this will continue indefinitely? The method of proof by using the principle of mathematical induction is frequently useful in the theory of numbers. Familiarity with this type of argument is essential to subsequent work.

## Is the base case required?

In any proof by induction, we must not forget to show that $0$ is in $P$.  Even if we show that the truth of $k$ in $P$ implies that $k+1$ is in $P$, if $0$ is not in $P,$ then we cannot conclude that $P$ is the set of positive integers.  For example, let $P$ be the set of all positive integers that satisfies:

$$\label{falseq} n+(n+1)=2n.$$

Suppose $k$ satisfies, \eqref{falseq}. Using this we have

$(k+1)+(k+2)=k+(k+1)+2=2k+2 = 2(k+1);$

and thus $k+1$ also satisfies \eqref{falseq}. So, if $1$ satisfies \eqref{falseq} then, it would follow that \eqref{falseq} is true for all positive integers $n$.  However, $0$ does not satisfy \eqref{falseq}. In fact, obviously, \eqref{falseq} is false for all positive integers $n$.  We conclude that the basis step is a necessary part of any proof by mathematical induction.

The assumption that “the statement is true for $n=1,2,3,\ldots,k$” will often be referred to as the induction hypothesis. Sometimes the role that 1 plays in the principle of mathematical induction will be replaced by some other integer, say $b,$ in such instances the principle of mathematical induction establishes the statement for all integers $n\geq b.$

The method of mathematical induction has its limitations in that it consists of testing a known (or conjectured) formula. All that the induction process enables us to do is to show that any special case can be proved on the assumption that all the preceding cases have been verified.

## What are mathematical induction principles?

Mathematical induction as an inference rule can be formalized as a second-order axiom.  The axiom of induction is, in logical symbols,

\begin{align*} & \forall P [ [ P(0) \land  \forall k \in \mathbb{N} (P(k) \Rightarrow P(k+1))]  \Rightarrow  \forall n \in \mathbb{N} [ P(n) ] ]  \end{align*}

where $P$ is any predicate and $k$ and $n$ are both positive integers.

In the hypothesis of mathematical induction, the statement $0\in P$ is called the base case.  Mathematical induction is really a collection of principles, for example, the base case may start at $0$, or $1$, or $2$, etc. instead of $0$.  In each of these scenarios the goal is to prove a collection of statements is true, for all $n$ greater than some initial value which must be verified (base case).

For example, while $n!>n$ is not true for $n=0, 1, 2$, it is true for all $n\geq 3$. So our base case is $n=3$. Let’s prove that $n!>n$ for all $n\geq 3$. Since $3!=1\cdot 2\cdot 3=6>3$ we see that the base case holds. Now assume that for some positive integer $k$ greater than 3, that $k!>k$. Then we see that

$$\label{factind} (k+1)!=k!(k+1)>k(k+1)>k+1.$$

Therefore, by mathematical induction, $n!>n$ for all $n\geq 3$.

Example.Prove that  $2^{n-1}>n$  for all positive integers $n\geq 3.$

Solution. Since $4=2^{3-1}=2^2=4>3$ the statement is true for $n=3.$ Assume that the result is true for a positive integer $n,$ we need to show that { }$2^{(n+1)-1}>n+1$ holds. Starting from $2^{n-1}>n$ we multiply by 2 to obtain $2^n>2n.$ But $2n=n+n>n+1$ since $n\geq 3.$ Therefore by mathematical induction, $2^{(n+1)-1}>2n>n+1$ for all positive integers $n\geq 3$ as desired. $\blacksquare$

## Conclusion

In this article, we’ve introduced mathematical induction and shown how it can be used to prove a statement is true for all natural numbers. We looked at a few examples, to help illustrate how induction works. We hope you found this information helpful and that it has given you a better understanding of mathematical induction. Do you have any questions about mathematical induction or anything we covered in this post? If so, please share them in the comments below and we’ll do our best to answer them.

In these 9 articles, you’ll learn about the basics of Mathematical Induction and how it can be used to prove mathematical statements. You’ll learn about the different types of inductions and how to apply them in various situations. These articles also include many examples (and exercises) for you to try on your own.

Also, don’t forget to check the video series on mathematical induction on YouTube.