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{aligned}1+3+\dots +(2k-1)+(2k+1)&=k^{2}+2k+1\\&=(k+1)^{2}\end{aligned}}$

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 {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{aligned}1+2+4+8+\dots +2^{k-1}+2^{k}&=2^{k}-1+2^{k}\\&=2(2^{k})-1\\&=2^{k+1}-1\end{aligned}}$

---

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\leq 2^{k+1}=2^{k}+2^{k}$, so $1\leq 2^{k}$... true

Add one to both side, so $k+1<2^{k}+1$. Since $1\leq 2^{k}$, adding $2^{k}$ to both sides gives $2^{k}+1\leq 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\geq 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{aligned}(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{aligned}}$

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