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:

John DoeSeptember 27, 2016 at 11:16 pmHow formal do you want the proofs in the homework to be? And why can I comment here without login/sign-up but need to for the forums for 341.

RobSeptember 28, 2016 at 7:01 amThe homework proofs don’t need to be overly formal. Aim for a level that is readable and would convince a skeptical student in our class.

As for the forums, that was a mistake on my part. It seems there was a separate setting I missed. Sorry about that! I have enabled anonymous posting in the forums, so you should be able to post there now.

John Doe?September 30, 2016 at 12:24 amThank you for the info and change,

can I stay as John Doe dough.

RobSeptember 30, 2016 at 7:57 amYep.