Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thanks in advance.

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?

share|improve this question
    
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. –  Vladimir Putin Aug 10 '12 at 23:36
1  
Who is the "he" you're all speaking about? –  Henning Makholm Aug 11 '12 at 0:52
1  
@Henning, probably the author(s) of the book OP is looking at. –  J. M. Aug 11 '12 at 0:54
1  
@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

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
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? –  Vladimir Putin 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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.