# Why does he need to first prove the sum of the $n$ integers and then proceed to prove the concept of arithmetical progression?

I'm reading What is Mathematics, on page 12 (arithmetic progression), he gives one example of mathematical induction while trying to prove the concept of arithmetic progression. There's something weird here: he starts by proving that the sum of the first $n$ integers is equal to $\frac{n(n+1)}{2}$ by giving this equation:

$$1+2+3+\cdots+n=\frac{n(n+1)}{2}.$$

Then he adds $(r+1)$ to both sides:

$$1+2+3+\cdots+n+(r+1)=\frac{n(n+1)}{2}+(r+1).$$

Then he solves it:

$$\frac{(r+1)(r+2)}{2}$$

Now it seems he's going to prove the arithmetical progression: He says that this can be ordinarily shown by writing the sum $1+2+3+\cdots+n$ in two forms:

$$S_n=1+2+\cdots+(n-1)+n$$

And:

$$S_n=n+(n-1)+\cdots+2+1$$

And he states that on adding, we see that each pair of numbers in the same column yields the sum $n+1$ and, since there are $n$ columsn in all, it follows that:

$$2S_n=n(n+1).$$

I can't understand why he needs to prove the sum of the first $n$ integers first. Can you help me?

EDIT: I've found a copy of the book on scribd, you can check it here. This link will get you in the page I'm in.

EDIT:
I kinda understand the proofs presented in the book now, but I can't see how they are connected to produce a proof for arithmetic progression, I've read the wikipedia article about arithmetic progression and this $a_n = a_m + (n - m)d$ (or at least something similar) would be more plausible as a proof to arithmetic progression - what you think?

-
Looks as if he is giving two different proofs. Good idea pedagogically. The first one is by induction. Either there is a major typo in it or it is not being quoted correctly. – André Nicolas Aug 10 '12 at 23:36
@Henry Yeah. I was thinking about how to centralize the LaTeX. – Voyska Aug 10 '12 at 23:36
Who is the "he" you're all speaking about? – Henning Makholm Aug 11 '12 at 0:52
@Henning, probably the author(s) of the book OP is looking at. – J. M. Aug 11 '12 at 0:54
@J.M.: Sure, but (a) it would have been polite to mention him by name, wouldn't it? And (b) there's at least one book of that title that has two authors. – Henning Makholm Aug 11 '12 at 16:07

He is giving two different proofs, one by a formal induction, and the other a more intuitive one. Good idea, two proofs makes the result twice as true! More seriously, he is probably taking this opportunity to illustrate proof by induction.

It is important to know the structure of a proof by induction. In order to show that a result holds for all positive integers $n$ one shows (i) that the result holds when $n=1$ and (ii) that for any $r$, if the result holds when $n=r$, then it holds when $n=r+1$.

(i) is called the base step and (ii) is called the induction step.

Almost always, the induction step is harder than the base step.

Here is how the logic works. By (i), the result holds when $r=1$. By (ii), because the result holds for $n=1$, it holds when $n=2$ (we have taken $r=1$). But because the result holds for $n=2$, it holds when $n=3$ (here we have taken $r=2$). But because the result holds when $n=3$, we can argue in the same way that the result holds when $n=4$. And so on.

In our example, suppose that we know that for a specific $r$, like $r=47$, we have $$1+2+\cdots+r=\frac{r(r+1)}{2.}$$ We want to show that this forces the result to hold for the "next" number. Add $(r+1)$ to both sides. We get $$1+2+\cdots +r+(r+1)=\frac{r(r+1)}{2}+(r+1).$$ Now we do some algebraic manipulation: $$\frac{r(r+1)}{2}+(r+1)=\frac{r(r+1)+2(r+1)}{2}=\frac{(r+1)(r+2)}{2},$$ which is what the formula we are trying to prove predicts when $n=r+1$. We have taken care of the induction step. The base step is easy. So we have proved that $1+2+\cdots+n=\frac{n(n+1)}{2}$ for every positive integer $n$.

Remark: Here is another way to think about the induction, one that I prefer. Suppose that there are positive integers $n$ for which the result is not correct. Call such integers $n$ bad. If there are bad $n$, there is a smallest bad $n$. It is easy to see that $1$ is not bad.

Let $r+1$ be the smallest bad $n$.

Then $r$ is good, meaning that $1+2+\cdots+r=\frac{r(r+1)}{2}$. Now we argue as in the main post that $1+2+\cdots +r+(r+1)=\frac{(r+1)(r+2)}{2}$. That shows that $r+1$ is good, contradicting the assumption that it is bad.

-
I kinda understand the proofs presented in the book, but I can't see how they are connected to produce a proof for arithmetic progression, I've read the wikipedia article about arithmetic progression and this $a_n = a_m + (n - m)d$ (or at least something similar) would be more plausible as a proof to arithmetic progression - what you think? – Voyska Aug 14 '12 at 11:27
If you are looking at $a+(a+d)+(a+2d)+\cdots +(a+(n-1)d)$ ($n$ terms) That's $na+d(1+2+\cdots+(n-1))$. Now use fact that $1+2+\cdots +(n-1)=(n-1)n/2$. Sorry if this is too brief, comments are not fun to type. Can also argue general AP by the trick of writing sum backwards, adding the two sums. – André Nicolas Aug 14 '12 at 13:08

He doesn't have to do both proofs. He's first using induction to illustrate the technique. Then he uses an easier method to show the same thing.

So, in the text, he begins by assuming $A_r:$

$$1 + 2 + 3+...+ r = \frac{r(r+1)}{2},$$ adds (r+1) to both sides to get

$$1 + 2 + 3 + ...(r+1) = \frac{(r+1)(r+2)}{2},$$ which is $A_{r+1}.$ It is clear that $A_r$ implies $A_{r+1}$ and since $A_1$ (i.e., $1 = \frac{1\cdot2}{2})$ is true, $A_r$ follows.

The second technique, which you set out in full in the question, is what the author feels is the ordinary (and somewhat shorter) way of showing the same thing.

On page 13 he goes on to give some motivation for going the extra mile with the induction, and says the same reasoning can be used to show the sum of $(n+1)$ terms of any arithmetical progression.

Hope this helps.

-

To add to daniel's answer, the statement $$A_n : \sum_{i = 1}^n i = \frac{n(n+1)}{2}$$ is true for all $n \in \Bbb{N}$ iff

1. $A_1$ is true. That is $1 = 1(1+1)/2 = 1.$

2. Whenever we assume $A_r$ is true, we can show that $A_{r+1}$ follows from $A_1$ and $A_{r}.$

This proof technique is called weak induction. Step 1 above is called the base case. Step 2 is called the inductive hypothesis: you assume a hypothesis you'd like to prove, and show that it actually follows for the successor number $r+1.$ Why? Well, intuitively, the natural numbers defined as: $$1, 1+1, 1+1+1, \ldots, r, r+1, \ldots$$ Show you show that a proposition hold for the first number, and for an arbitrary adjacent pair. You'll find more on the topic induction in the book or in Wikipedia.

-