Proof by Induction

Proof By Induction

Definition

A proof by induction of $P(n)$, a mathematical statement involving a value $n$, involves these main steps:

  • Basis Case - Prove directly that $P$ holds for the initial value of $n$ (usually zero or one)
  • Inductive Hypothesis - Assume for some value $k$ that $P(k)$ holds
  • Inductive Step - Directly prove that $P(k)\Rightarrow P(k+1)$. That means prove directly that $P(k+1)$ holds by using the fact that $P(k)$ holds.
Worked Examples
Example 1

Prove by induction that $n^3+2n$ is divisible by 3 for every non-negative integer $n$.

Solution

Let $P(n)$ be the mathematical statement $n^3+2n$ is divisible by 3.

Basis Case: When $n=0$, we have $0^3+0 = 0 = 3 \times 0$. So $P(0)$ holds.

Inductive Hypothesis: Assume that $P(k)$ holds for some positive integer $k$. That means $k^3+2k$ is divisible by 3 and hence that $k^3+2k =3m$ for some integer $m$.

Inductive Step: Now show that $P(k+1)$ holds. Take the original formula and replace the $n$ with $k+1$ to get $(k+1)^3+2(k+1)$ and we will show that this is divisible by 3. At some stage in the proof we will need to use the fact that $k^3+2k=3m$, so when rearranging the formula we try to get $k^3+2k$ as part of it:

\begin{align} (k+1)^3+2(k+1) &= k^3+3k^2+3k+1+2k+2\\ &=k^3+2k+ 3(k^2+k+1)\\ &=3m + 3(k^2+k+1)\\ &=3(m+k^2+k+1) \end{align}

As $m+k^2+k+1$ is an integer we have that $(k+1)^3+2(k+1)$ is divisible by 3, so $P(k+1)$ holds. Hence by induction $P(n)$ holds for all non-negative integers $n$.

Example 2

Prove by induction that $2^n \gt 2n$ for every positive integer $n\gt 2$.

Solution

Let $P(n)$ be the mathematical statement $2^n\gt 2n$.

Basis Case: When $n=3$, we have $2^3=8\gt 6=2\times 3$. So $P(3)$ holds.

Inductive Hypothesis: Assume that $P(k)$ holds for some positive integer $k$. That means $2^k\gt 2k$.

Inductive Step: Now show that $P(k+1)$ holds. By the inductive hypothesis,

\begin{align} 2^{k+1} = 2 \times 2^k & \gt 2 \times 2k \\ & \gt 2(k+1) \end{align}

So $P(k+1)$ holds. Hence by induction $P(n)$ holds for all positive integers $n\gt 2$.

External Resources