Proof by Induction

The first is about sums of even numbers. Proofs about sums of infinite sets of natural numbers lend themselves well to proof by induction.

Proof. We will prove that equation (1) holds for all natural numbers by induction.

For the basis step we consider \(n = 1\). Then

\begin{align*} \sum _{i=1}^n 2i &= \sum _{i=1}^1 2i \\ &= 2 \\ &= 1(1+1) \end{align*}

So we have established that Equation (1) holds when \(n=1\).

We now turn to the induction step. We assume

\begin{equation*} \sum _{i=1}^k 2i = k(k+1) \end{equation*}

for some natural number \(k \ge 1\). We then show that Equation (1) holds for \(k+1\) as follows:

\begin{align*} \sum _{i=1}^{k+1} 2i &= \sum _{i=1}^{k} 2i + 2(k+1) \\ &= k(k+1) + 2(k+1) \\ &= (k+1)(k+2) \\ &= (k+1)(k+1+1) \end{align*}

Since we have now proved that Equation (1) holds for \(n=1\) and that if it holds for \(n=k\) it also holds for \(n=k+1\), we have shown by induction that for all natural numbers \(n\)

\begin{equation*} \sum _{i=1}^n 2i = n(n+1) \end{equation*}

□