MATH 302 Lecture 11

« previous | Wednesday, October 5, 2011 | next »

Mathematical Induction Examples

Theorem. The sum of the first $n$ odd positive integers is $n^2$

Proof by Induction. Let $P(n)=\sum _{i=1}^{n}2i-1=n^2$

Basis Step. For $P(1)$, $1=1^2$ is true.

Inductive step. For some arbitrary integer $k$ greater than zero, assume that $P(k)$ is true:

$1+3+\dots +(2k-1)=k^2$

We add $2k+1$ to both sides, so

$\begin{array}{rl}1+3+\dots +(2k-1)+(2k+1)& =k^2+2k+1\\ & =(k+1{)}^2\end{array}$

This proves $P(k+1)$ and thus the inductive step.

By the principle of mathematical induction, $P(n)$ is true for all $n\in \mathbb{\mathbb{N}}$

---

Theorem. The sum of the first $n$ powers of 2 is equal to $2^n-1$:

$1+2+4+8+\dots +2^{n-1}=2^n-1$

Proof by Induction. Let $P(n)$ represent the proposition $\sum _{k=1}^n{2}^{k-1}=2^n-1$.

Basis step. For $P(1)$, we have $1=2-1$, which is true.

Inductive step. For any arbitrary integer $k>0$, assume that $P(k)$ is true, so

$1+2+4+8+\dots +2^{k-1}=2^k-1$

.

Let's add the next term $2^k$ to both sides:

$\begin{array}{rl}1+2+4+8+\dots +2^{k-1}+2^k& =2^k-1+2^k\\ & =2(2^k)-1\\ & =2^{k+1}-1\end{array}$

---

Theorem. For $n>0$, $n<2^n$

Proof by Induction.

Basis step. $1<2$, so true.

Inductive step. For some arbitrary integer $k>0$, assume $P(k)$ is true.

SCRATCH PAPER:

Target: $k+1<2^{k+1}$

Extra inequality: $2^k+1\le 2^{k+1}=2^k+2^k$, so $1\le 2^k$... true

Add one to both side, so $k+1<2^k+1$. Since $1\le 2^k$, adding $2^k$ to both sides gives $2^k+1\le 2^k+2^k=2^{k+1}$.

Combining these two inequalities gives $k+1<2^{k+1}$, proving $P(k+1)$ and the inductive step.

Then $P(n)$ is true in general by the principle of mathematical induction.

---

Theorem. $5|n^5-n$ for all $n\ge 1$. In other words, there is an integer $l$ so that $5l=n^5-n$.

Proof by Induction.

Basis step. $5|1-1$… true since all numbers divide zero.

Inductive step. For some arbitrary integer $k$, assume $P(k)$ is true, so $5|k^5-k$.

SCRATCH PAPER:

Target: $5|(k+1{)}^5-(k+1)$, so we need to find that $5l=k^5-k$ can be expanded to look like the original statement.

$\begin{array}{rl}(k+1{)}^5-(k+1)& =k^5+5k^4+10k^3+10k^2+5k+1-(k+1)\\ & =(k^5-k)+5k^4+10k^3+10k^2+5k\\ & =5l+5k^4+10k^3+10k^2+5k\\ & =5(l+k^4+2k^3+2k^2+k)\end{array}$

For some integer $l$, $5l=k^5-k$