# Is this backwards reasoning?

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

-
(2) is not assuming for "$k=1$", but rather, it is assuming in generality for "$k+1$". – cygorx Jan 6 '14 at 22:08
Could you please explain it better? Because I did not understand a single word – Ant Jan 6 '14 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 '14 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 '14 at 22:19
@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 '14 at 22:37

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.

-
well precisely what I was thinking.. It's just a communication problem, not a technical one – Ant Jan 6 '14 at 22:25
@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 '14 at 22:30
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 '14 at 22:36
@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 '14 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").

-
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 '14 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 '14 at 1:11
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 '14 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.

-

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 $=$.

-

If you want to present a proof in the way you discovered it you could indeed do it this way:

To prove $A$, it suffices to prove $B$, which is equivalent to $C$, ...

Or in symbolic form:

We have:

$A$

$\ \Leftarrow B$

$\ \Leftrightarrow C$.

$\ \cdots$

In both cases, the logical reasoning is made clear without going in the 'opposite direction' to the way you found the proof.

Just to make sure people don't think that simplification to $0=0$ means that an equation is true, find the logical error in the following fake proof:

We want to prove $\sqrt{x^2+1} = x \sqrt{1+\frac1{x^2}}$ for every $x \ne 0$, and we proceed by squaring and simplifying:

$x^2+1 = x^2 ( 1 + \frac1{x^2} )$.

$x^2+1 = x^2+1$.

Therefore we (WRONGLY) conclude that the claim is proven.

Many students would see nothing wrong, so dear reader, please make sure you know precisely what is wrong.

-
You are right, of course. But I want to point out that everyone does what I did all the time; If I give you an equation like $x^2 - (3x + 7)(2x - 1) = 9$, what do you do? You simplify and solve the quadratic. Ah! But aren't you going then in the wrong direction? You should start from the final quadratic form, add and subtract stuff until you get the original form I gave you, then tell me the solutions are the same. We never do that because it is well understood that each step is reversible, and so neither did I in the proof. – Ant 2 days ago
"everyone does what I did all the time" is perhaps true among many (but not all) high-school students, but this is a vicious circle because they were in turn taught by teachers who didn't learn mathematics properly, or following syllabuses that don't care about valid reasoning, and so on. In fact, if you gave the high-school me an equation like that I wouldn't simplify and solve just like that. I would write: "For any real $x$, we have $x^2 - (3x+7)(2x-1) = 9$ iff $5x^2 + 11x + 2 = 0$ iff either $x = ?$ or $x = ?$." – user21820 2 days ago
@Ant: Perhaps you don't see the seriousness of the problem. That's fine. Take a look at the links in my profile under the last section, as well as examples of bad pedagogy at matheducators.stackexchange.com/a/9917/1550 and matheducators.stackexchange.com/q/9994/1550. – user21820 2 days ago
@Ant: Anyway if one is really lazy to maintain reversible implications when solving an equation, one can say "This gives ... and then ... and therefore $x \in ?$. We can now check that the only solutions are ..." If a student does not do/state the final step, and does not explicitly use bi-implications, then it is highly likely that the student actually cannot perform correct logical reasoning! I'm sure that if you teach enough you'll agree with me. – user21820 2 days ago
Well given that you have (much) more experience than me I will agree with you at this point, but from my point of view it is not a serious problem if one knows what he's doing. Then again I have only seen me do that, so I can be wrong :) – Ant 2 days ago