Example: A Proof by Induction

///Example: A Proof by Induction

Example: A Proof by Induction

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
By | 2017-01-01T15:25:37+00:00 September 22nd, 2016|Categories: Courses, Math 341|Tags: |4 Comments

4 Comments

  1. John Doe September 27, 2016 at 11:16 pm - Reply

    How 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.

    • Rob September 28, 2016 at 7:01 am - Reply

      The 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 am - Reply

        Thank you for the info and change,
        can I stay as John Doe dough.

        • Rob September 30, 2016 at 7:57 am - Reply

          Yep.

Leave A Comment

This Is A Custom Widget

This Sliding Bar can be switched on or off in theme options, and can take any widget you throw at it or even fill it with your custom HTML Code. Its perfect for grabbing the attention of your viewers. Choose between 1, 2, 3 or 4 columns, set the background color, widget divider color, activate transparency, a top border or fully disable it on desktop and mobile.

This Is A Custom Widget

This Sliding Bar can be switched on or off in theme options, and can take any widget you throw at it or even fill it with your custom HTML Code. Its perfect for grabbing the attention of your viewers. Choose between 1, 2, 3 or 4 columns, set the background color, widget divider color, activate transparency, a top border or fully disable it on desktop and mobile.