Skip to main content

Section 1.3 Induction

This follows immediately from the fact that \(\mathbb{N}\) has a least element.

Suppose that the theorem is not true. Thus there exist \(a,b\in\mathbb{N}\) for which \(na\lt b\) for all \(n\in\mathbb{N}.\) Consider the set

\begin{equation*} S = \{b-na:n\in\mathbb{N}\}. \end{equation*}

Clearly \(S\subset \mathbb{N},\) so by the Well-Ordering Principle, \(S\) contains a least element, say \(b-ka.\) Since \(k+1\in\mathbb{N},\) we have also \(b-(k+1)a\in S.\) But

\begin{equation*} b-(k+1)a=(b-ka)-a\lt b-ka, \end{equation*}

a contradiction. Hence the theorem is true.

Let \(S\subset\mathbb{N}\) with \(1\in S\) and with the property that if \(k\in S,\) then \(k+1\in S.\) Toward a contradiction, write \(T=\mathbb{N}\backslash S,\) and assume \(T\neq \emptyset.\) Note that \(T\subset\mathbb{N},\) so that by the Well-Ordering Principle, \(T\) contains a least element, say \(t\) (this also means \(t\notin S\)). Since \(1\in S,\) \(t\gt 1,\) and so \(0 \lt t-1 \lt t.\) Since \(t\in T\) is the smallest element and \(t-1\in\mathbb{N},\) it must be the case that \(t-1\in S.\) But by the definition of \(S\) since \(t-1\in S,\) we have \(t\in S,\) a contradiction. Thus \(T=\emptyset,\) and \(S=\mathbb{N}.\)

Remark 1.3.5.

Note that here the set \(S\) may be a solution set to a certain equality or inequality. The only condition is that \(S\subset\mathbb{N}.\) The following theorem demonstrates this.

To show that this is true for all \(n\in\mathbb{N}\) we need only show that conditions \((i)\) and \((ii)\) of Theorem 1.3.4 hold. To this end, note that

\begin{equation*} 1=\sum_{i=1}^{1}i=\frac{1(1+1)}{2}=1 \end{equation*}

so condition \((i)\) is satisfied. To see condition \((ii)\) holds, let us suppose that

\begin{equation*} \sum_{i=1}^{n}i=\frac{n(n+1)}{2}. \end{equation*}

Now consider the \(n+1\) case. We have

\begin{align*} \sum_{i=1}^{n+1}i \amp=\left(\sum_{i=1}^{n}i\right)+(n+1)\\ \amp =\frac{n(n+1)}{2}+(n+1)\\ \amp =\frac{n(n+1)+2(n+1)}{2}\\ \amp =\frac{n^2+2n+2}{2}\\ \amp =\frac{(n+1)(n+2)}{2}\\ \amp =\frac{(n+1)((n+1)+1)}{2} \end{align*}

and so by induction for all \(n\in\mathbb{N}\) we have

\begin{equation*} \sum_{i=1}^{n}i=\frac{n(n+1)}{2}. \end{equation*}

Induction is not always needed. Indeed, we may prove the above theorem without using induction.

Let \(n\in\mathbb{N}.\) Since addition is commutative we have that

\begin{align*} \sum_{i=1}^{n}i \amp=1+2+3+...+(n-1)+n\\ \amp + \\ \sum_{i=1}^{n}i \amp=n+(n-1)+...+3+2+1\\ \Rightarrow 2\sum_{i=1}^{n}i \amp=n(n+1) \end{align*}

So we have that for an arbitrary \(n\in\mathbb{N}\)

\begin{equation*} \sum_{i=1}^{n}i=\frac{n(n+1)}{2}. \end{equation*}

As before, we must show that conditions \((i)\) and \((ii)\) of Theorem 1.3.4 hold.

For \((i),\) it is quite straightforward to see that

\begin{equation*} 1=\frac{m-1}{m-1}, \end{equation*}

and so the result holds for \(k=1.\)

For \((ii)\) suppose the result holds for \(k\gt 1.\) Then

\begin{align*} 1+m+m^2+...+m^{k-1}+m^k \amp=\frac{m^k-1}{m-1}+m^k\\ \amp=\frac{m^k-1}{m-1}+\frac{m^k(m-1)}{m-1}\\ \amp=\frac{m^k-1+m^{k+1}-m^k}{m-1}\\ \amp=\frac{m^k-1}{m-1}, \end{align*}

so the result holds for \(k+1.\) Thus for \(m\gt 1\) and all \(k\in\mathbb{N}\) we have

\begin{equation*} 1+m+m^2+...+m^{k-1}=\frac{m^k-1}{m-1}. \end{equation*}

As we will use induction in a different (and equivalent form) in the coming lectures, we put it down for the record now.