You may comfortable with the logic of mathematical induction, but still feel uncomfortable with how to actually write up the proof. So here is an example taken from class today, presented in several different ways. Let’s prove the following:

Claim. For every integer $n\geq 1$ the following equality holds: $$\sum_{i=1}^n (2i-1)= n^2.$$

In other words, we are claiming that the sum of the first $n$ odd integers equals $n^2$. We will give several different proofs. None are particularly eloquent, but hopefully they will at least give you a flavor for the type of language you might use in writing up such a proof.

A Careful Proof by Induction

Following the notation in our textbook, let $S$ be the set of all positive integers $n$ for which the claim is true. Observe that the claim is true for $n=1$ (since $1 = 1^2$), so $1\in S$. (That was our base case.) Now suppose that $k\in S$ for some positive integer $k$. In other words, suppose the claim is true for some positive integer $k$, i.e.,  $\sum_{i=1}^k (2i-1)=k^2$. (This is our induction hypothesis.) We must show that $k+1\in S$, i.e., that the claim is true for $k+1$. In other words, we must show (somehow) that $\sum_{i=1}^{k+1} (2i-1) = (k+1)^2$. We now observe the following:

\begin{align*}
\sum_{i=1}^{k+1} (2i-1) &= \left(\sum_{i=1}^k (2i-1)\right) + \left(2(k+1)-1\right)\quad \text{(splitting off the last term from the sum)}\\
&= \left(\sum_{i=1}^k (2i-1)\right)+2k+1\quad \text{(simplifying)}\\
&= k^2+2k+1\quad \text{(by our induction hypothesis!)}\\
&= (k+1)^2.
\end{align*}

We have thus proven that the claim is true for $k+1$. By induction, it follows that the claim is true for all $n\geq 1$.

A Casual Proof by Induction

The above proof is fine, if a bit wordy. Here is a more informal proof. We proceed by induction. The case $n=1$ is clear. Suppose now the claim holds for some positive integer $k$. Then observe that

\[
\sum_{i=1}^{k+1} (2i-1) = \left(\sum_{i=1}^k (2i-1)\right) + 2k+1 = k^2+2k+1 = (k+1)^2,
\] where the second equality held by the induction hypothesis. We’ve therefore proven that the claim holds for $k+1$, and hence the claim is true for all $n\geq 1$.

A Proof without Induction

Here is a third proof, that hides the induction by relying on the fact that we already proved (in class, by induction) that $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ for all $n\geq 1$. Observe that
\[
\sum_{i=1}^n (2i-1) = 2\sum_{i=1}^n i – \sum_{i=1}^n 1 = 2\cdot \frac{n(n+1)}{2}-n = n(n+1)-n = n^2.
\]

There are countless other proofs of this claim, some quite surprising. Here is a so-called proof without words, stolen from Wikipedia:

A proof without words