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.

Yesterday I was answering a question on induction: Certain step in the induction proof $\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ unclear

Basically, I was proving a certain formula using induction.

$$\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$

The base case it's okay. Now let's assume the formula is valid for $N$, we want to demonstrate the following, that is

$$\sum\limits_{i=0}^{N+1} i^2 = \frac{(N+1)(N+2)(2(N+1)+1)}{6} \ \ (1) $$

that is to say

$$\sum\limits_{i=0}^{N} i^2 + (N + 1)^2 = \frac{(N+1)(N+2)(2(N+1)+1)}{6}\ \ (2) $$

$\Rightarrow$ (thanks to induction hypothesis)

$$\frac{N(N+1)(2N+1)}{6} + (N+1)^2 = \frac{(N+1)(N+2)(2(N+1)+1)}{6}\ \ (3) $$

Then I concluded that if one show that (3) is true (by simplifying, and getting $0 = 0$) then the proof is valid and complete.

Some argue this is backwards reasoning; but I can't understand why.

The equalities that I use to go from (1) to (2) to (3) can be used for going from (3) to (2) to (1)

My argument is, if (3) simplifies to $0=0$, so it is equivalent with that and therefore True, also (2) is True, and also (1) is true, which was what I wanted to prove.

Is this backwards reasoning, and if so someone please explain me why

share|improve this question
    
(2) is not assuming for "$k=1$", but rather, it is assuming in generality for "$k+1$". –  cygorx Jan 6 at 22:08
    
Could you please explain it better? Because I did not understand a single word –  Ant Jan 6 at 22:12
    
Sorry. When proving by induction, you first prove it is true for some variable $k = 0$ (or $k = 1$). You then prove that--if $k = 1$ is true, and assume $k = 2$ (or $k = 1$ in the former case)--it is true for $k = k + 1$. This is not a valid mathematical induction because it does not properly follow those two steps. –  cygorx Jan 6 at 22:16
    
Ah okay.. I didn't prove the base case because it's quite trivial, but the rest of the proof is there. I should have specified , though, that I was assuming the statement true for N and than demonstrating it for N + 1. Now it should be clear what I meant –  Ant Jan 6 at 22:19
1  
@Ant Be careful, $\pi = \sin^{-1} 0$ also simplifies to $0 = 0$ (if you take the sine of both sides), but it doesn't make the first statement true. –  Erick Wong Jan 6 at 22:37

4 Answers 4

up vote 5 down vote accepted

EDIT: The question has been updated, so the answer is mostly irrelevant (but it still shows how one word here or there can change quite a lot :-) )


I don't think your reasoning was backwards, but its presentation and wording might have been understood so. Specifically, stating "we have" implies it's something we either assume or have already proven rather than something we're trying to prove. Presenting the same reasoning slightly differently could avoid the ambiguity:

Let's evaluate the sum for $N+1$: $$\sum_{i=1}^{N+1} i^2 = \sum_{i=1}^{N} i^2 + (N+1)^2$$ The induction hypothesis tells us that $$\sum_{i=1}^{N} i^2 = \frac{1}{6}N(N+1)(2N+1)$$ so $$\sum_{i=1}^{N} i^2 + (N+1)^2 = \frac{1}{6}N(N+1)(2N+1) + (N+1)^2$$ Simplifying the right-hand side yields $$\frac{1}{6}N(N+1)(2N+1) + (N+1)^2 = \frac{1}{6}(N+1)\left((N+1)+1\right)\left(2(N+1)+1\right)$$

Finally, combining the equalities shows that the statement holds for $N+1$ as well, thus completing the inductive step.

share|improve this answer
1  
well precisely what I was thinking.. It's just a communication problem, not a technical one –  Ant Jan 6 at 22:25
1  
@Ant Barring difficulties with foreign languages, communication problems are often viewed as symptomatic of imprecise thinking, which is a type of technical problem. Here's an example: you said "The equalities that I use to go from (1) to (2) to (3) can be used for going from (3) to (2) to (1) (of course, being equality relations symmetric)", but the symmetry of equality has nothing to do with the reversibility of the logic from (1) to (2) to (3). –  Erick Wong Jan 6 at 22:30
2  
You're absolutely right; I am not a native english speaker as you can see, and it's kinda difficult to translate in a precise manner technical stuff. After you pointed that out,I can see that the comment is indeed wrong; I'll edit it) –  Ant Jan 6 at 22:36
1  
@Ant Thanks, actually I hadn't at all noticed that you weren't a native English speaker: your grammar and spelling could have fooled me! :) –  Erick Wong Jan 6 at 22:40

It is a common misconception for students that you can prove $A=B$ by showing that it simplifies to $0=0$. Often times this is a bad habit picked up from observing others who find it convenient to work this way (and who may or may not understand when it is logically sound). But this is generally a bad practice because it really is backwards reasoning; like Peter Košinár, I won't go so far as to accuse you of this, but the order that your proof is written can easily be interpreted this way.

When doing things in this order (starting from $A=B$ and simplifying down to $0=0$), once has to take extra care that every operation is perfectly reversible. Adding the same thing to both sides is reversible by subtraction. Multiplying both sides by the same quantity is reversible by division...unless it's possible that the multiplier is $0$! Squaring both sides is potentially reversible, provided they were known to be non-negative to begin with.

So when you write out a proof in this order, what you are doing is placing a burden on yourself to consider the reversibility of every single step (or if you don't mention this, you place the burden on the reader). And if you're going to have to explicitly reverse each step anyway, it's almost always the case that it's simpler to just write it down in logical order in the first place (starting from a known truth and ending up at $A=B$).

One of the conventions of mathematical writing is that we strive to present arguments in a logical order of deduction, starting from true facts and building more and more true facts until we reach the desired conclusion. This convention is not necessarily obvious or natural: it might feel better to explain your thinking process in chronological order ("first I did this, then I calculated that, and that's why I did this to both sides").

Mathematical analysis is full of proofs that are written in exactly the opposite order as the discovery process — this might seem strange to you, but it is the standard convention and it is what your readers will expect. (That's not to say every proof needs to be written mechanically from basic premises to final conclusion: many times an author can improve the readability of a long proof by using abridgments like "we'll use this fact, whose proof is deferred to the appendix", or annotations like "we chose this because such-and-such will be needed later in Section 3").

share|improve this answer
    
Of course I'm aware of that. And next time I'll bear that in mind and try to conform with the standards, but I have to say that with proof by induction, I find this methodology particularly fitted. I mean, the order in which I present the proof may be a little misleading, but it's pretty clear (I think) why I'm doing what I'm doing. Starting off with "We know that $0=0$. Let's add $N$; then divide by $6$; then... and so on as to finally arrive to the desired expression feels somehow weird. Though you're right that one has to explicitly control every step –  Ant Jan 6 at 23:21
    
@Ant Absolutely agree that it feels weird, but the way to fix it is to rephrase it so that it doesn't feel weird, rather than to write $A \Rightarrow B$ when you mean $B \Rightarrow A$. A quick fix in your simple case would just be to use expressions like "this is equivalent to" (with whatever justification might be warranted) rather than your use of "that is" (which is not wrong, but reads a bit ambiguously) or "$\Rightarrow$" (which really is backwards). –  Erick Wong Jan 7 at 1:11
1  
To show that $A=B$ you just need to show that $A-B=0$, you don't necessarily need to show that you can construct the form of $B$ from $A$ with more or less tricky algebraic manipulations. –  Jostein Trondal Jan 7 at 7:19

Equation (1) uses the formula to sum the terms from $0$ to $N+1$, by replacing $N$ with $N+1$ everywhere on the right side. Check.

The left side of equation (2) sums the terms from $0$ to $N$, and adds the $(N+1)$th term explicitly. Check.

The left side of equation (3) makes use of the assumption that the equation holds for terms summed from $0$ to $N$. Check.

Explicit calculation of the left side of (3) results in the same expression as you found on the right side of (1). Check.

So you've got all of the pieces there; you just need to arrange them a bit differently and change the phrasing in between the steps.

share|improve this answer

How about this.

To show that $$L(n)=\sum_{i=1}^{n}a_i=R(n)$$ holds for all $n$, you use induction. Step 1: Show that $$L(1)-R(1)=0.$$ Step 2: Show that $$L(n)=R(n)\quad\Rightarrow\quad L(n+1)=R(n+1).$$ Since $L(n+1)=L(n)+a_{n+1}$, we have $$L(n)=R(n)$$ $$L(n)+a_{n+1}=R(n)+a_{n+1}$$ $$L(n+1)=R(n)+a_{n+1}$$ so we need to show that $$R(n)+a_{n+1}=R(n+1)\qquad(1)$$ The standard method (let us call it method A) to show $(1)$ is to try to construct the form of $R(n+1)$ from $R(n)+a_{n+1}$. An alternative method (method B) is simply to check if $$R(n)+a_{n+1}-R(n+1)=0.$$ It is usually much easier to do method B, as you don't need to come up with any tricks from algebra. Just expand and simplify. If you get $0$, you're home free. In fact we can do better than this. It is sufficient to show that $$k\cdot[R(n)+a_{n+1}-R(n+1)]=0$$ for some nonzero $k$. This means that you can get rid of troublesome fractions on your way by multiplying by them. If you do that, you should write $\propto$ instead of $=$.

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.