## You are here

Homean example of mathematical induction

## Primary tabs

# an example of mathematical induction

Below is a step-by-step demonstration of how mathematical induction (the Principle of Finite Induction) works.

###### Proof.

Setup. Let $S$ be the set of positive integers $n$ satisfying the rule: $2^{{n-1}}\leq n!$. We want to show that $S$ is the set of *all* positive integers, which would prove our proposition.

Initial Step. For $n=1$, $2^{{n-1}}=2^{{1-1}}=2^{0}=1$, while $n!=1!=1$. So $2^{{n-1}}=n!$ for $n=1$ and thus $2^{{n-1}}\leq n!$ all the more so. This shows that $1\in S$.

Induction Step 1. Assume that for $n=k$, $k$ a positive integer, $2^{{n-1}}\leq n!$. In other words, we assume that $k\in S$, or that $2^{{k-1}}\leq k!$.

Induction Step 2. Next, we want to show that $k+1\in S$. If we let $n=k+1$, then by the assumption of the proposition, showing $n=k+1\in S$ is the same as showing $2^{{n-1}}\leq n!$, or $2^{k}\leq(k+1)!$. This can be done by the following calculation:

$\displaystyle 2^{k}$ | $\displaystyle=$ | $\displaystyle 2^{{k-1}}2$ | (1) | ||

$\displaystyle\leq$ | $\displaystyle k!2$ | (2) | |||

$\displaystyle\leq$ | $\displaystyle k!(k+1)$ | (3) | |||

$\displaystyle=$ | $\displaystyle(k+1)!,$ | (4) |

where Equations (1) and (4) are just definitions of the power and the factorial of a number, respectively. Step (3) is the fact that $2\leq k+1$ for any positive integer $k$ (which, incidentally, can be proved by mathematical induction as well). Step (2) follows from the *induction step*, the assumption that we made in the Induction Step 1. in the previous paragraph. Because $2^{k}\leq(k+1)!$, we have thus shown that $n=k+1\in S$, proving the proposition.
∎

Remark. All these steps are essential in any proof by (mathematical) induction. However, in more advanced math articles and books, some or all of these steps are omitted with the assumption that the reader is already familiar with the concepts and the steps involved.

## Mathematics Subject Classification

00A05*no label found*00A35

*no label found*03E25

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new image: information-theoretic-distributed-measurement-4.2 by rspuzio

new image: information-theoretic-distributed-measurement-4.1 by rspuzio

new image: information-theoretic-distributed-measurement-3.2 by rspuzio

new image: information-theoretic-distributed-measurement-3.1 by rspuzio

new image: information-theoretic-distributed-measurement-2.1 by rspuzio

Apr 19

new collection: On the Information-Theoretic Structure of Distributed Measurements by rspuzio

Apr 15

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz