Induction

For proof by induction that a statement is true for all $n\ge 1$ we show two things:

• That the statement is true for $n=1$.
• That if some statement is true for $n=k$, it must also be true for $n=k+1$

Then, since it's true for $n=1$, it must also be true for $n=1+1=2$, and since it's true for $n=2$, it must also be true for $n=2+1=3$, and so on, ad infinitum.

Example

We will prove by induction that

$$\begin{array}{cc}{1}^2+2^2+3^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6}& \text{(a)}\end{array}$$

First, let's show that for $n=1$ the equation is true:

$$\begin{array}{cc}{1}^2=\frac{1(1+1)(2\cdot 1+1)}{6}=1& \text{(b)}\end{array}$$

Now we must show that if we assume the equation is true for $n=k$:

$$\begin{array}{cc}{1}^2+2^2+3^2+\cdots +k^2=\frac{k(k+1)(2k+1)}{6}& \text{(c)}\end{array}$$

then it is also true for $n=k+1$, that is that:

$$\begin{array}{cc}{1}^2+2^2+3^2+\cdots +(k+1{)}^2=\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}& \text{(d)}\end{array}$$

is true.

Since we assume that $(c)$ is true, then adding $(k+1{)}^2$ to both sides in $(c)$ must also result in a true equation:

$$\begin{array}{cc}{1}^2+2^2+3^2+\cdots +k^2+(k+1{)}^2=\frac{k(k+1)(2k+1)}{6}+(k+1{)}^2& \text{(e)}\end{array}$$

By combining terms on the right side and factoring, we get that:

$$\begin{array}{cc}{1}^2+2^2+3^2+\cdots +k^2+(k+1{)}^2=\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}& \text{(e)}\end{array}$$

must be true, which is what we set out to show.

Thus, since we have shown that $(a)$ is true for $n=1$, and that if it is true for $n=1$ it must also be true for $n=1+1=2$, then it must also be true for $n=2$, and therefore also true for $n=2+1=3$, and so on, ad infinitum $◼$.

Another Example

Prove that for all $n\ge 0$:

$$\begin{array}{cc}\sum _{k=0}^n{3}^k=\frac{3^{(n+1)}-1}{2}& \text{(a)}\end{array}$$

Proof

We will proceed using proof by induction.

Base Case

First, we must show that the base case where $n=0$ is true.

Substituting $0$ for $n$ into (a) gives

$$\begin{array}{cc}\sum _{k=0}^0{3}^k=\frac{3^{0+1}-1}{2},& \text{(b)}\end{array}$$

and we can simplify both sides to get

$$\begin{array}{cc}{3}^0=\frac{3^1-1}{2},& \text{(c)}\end{array}$$

which reduces to

$$\begin{array}{cc}1=1,& \text{(d)}\end{array}$$

which is obviously true and shows that (a) is true for the base case where $n=0$.

Induction Case

Now we must show that if we assume (a) is true for some $n\ge 0$, that (a) is also true for $n+1$.

That is, we must show that if we assume

$$\begin{array}{cc}\sum _{k=0}^n{3}^k=\frac{3^{(n+1)}-1}{2}& \text{(e)}\end{array}$$

is true, that

$$\begin{array}{cc}\sum _{k=0}^{(n+1)}{3}^k=\frac{3^{(n+1)+1}-1}{2}& \text{(f)}\end{array}$$

is necessarily true.

Now, assume (e) is true.

Using the fact that the summation on the left hand side of (f) is short hand for the series

$$\begin{array}{cc}{3}^0+3^1+3^2+\cdots +3^n+3^{(n+1)},& \text{(g)}\end{array}$$

we can rewrite (f) as

$$\begin{array}{cc}{3}^0+3^1+3^2+\cdots +3^n+3^{(n+1)}=\frac{3^{(n+1)+1}-1}{2}& \text{(h)}\end{array}$$

Now, the terms on the left-hand side of (h) are just

$$\begin{array}{cc}\sum _{k=0}^n{3}^k+3^{(n+1)}& \text{(i)}\end{array}$$

so we have

$$\begin{array}{cc}\sum _{k=0}^n{3}^k+3^{(n+1)}=\frac{3^{(n+1)+1}-1}{2}& \text{(j)}\end{array}$$

Since we assumed that (e) is true, we can replace the summation on the left-hand side of (j) with its equivalent on the right-hand side of (e) to get

$$\begin{array}{cc}\frac{3^{(n+1)}-1}{2}+3^{(n+1)}=\frac{3^{(n+1)+1}-1}{2}.& \text{(k)}\end{array}$$

Combining terms on the left-hand side gives

$$\begin{array}{cc}\frac{3(3^{(n+1)})-1}{2}=\frac{3^{(n+1)+1}-1}{2},& \text{(l)}\end{array}$$

and since $3(3^{(n+1)})=3^{(n+1)+1}$ we get that

$$\begin{array}{cc}\frac{3^{(n+1)+1}-1}{2}=\frac{3^{(n+1)+1}-1}{2},& \text{(m)}\end{array}$$

is necessarily a true statement, which is what we needed to show. $◼$