Hacker News Reader

Comment by silentvoice | Hacker News Reader

One of the most bizarre errors I've seen undergraduates make is in induction proofs. I saw it so many times that I decided a TA must have been telling them to do this.

They would always show the base case correctly. Then they assume it's true for all positive integers up to a fixed positive integer "n." So far so good, now we need to prove it's true for "n+1." This is where weirdness happens, I have seen a hundred assignments where an equation is reduced down to "0=0" or "1=1" and they then write "Q.E.D" even though the fact that 0=0 was not under contest.

View on HN

All horses are of the same color.

By induction, suppose there are only n=1 horses. Obviously they are all the same color.

Suppose we had proven the statement up to n. For every n+1 horses, the first n horses must be the same color. The last n horses too, must have the same color. Clearly all of them have the same color. QED.

This is lovely -- very simple, but my error-finding intuition started me off entirely in the wrong direction.

I admit I laughed heavily when I saw that as the first warm up in Concrete Mathematics.

And then just breathed deeply with how quickly it got beyond me. :)

I'd guess it's probably because they don't actually understand proofs in the first place. There are a lot of computer science undergrads who go in with math only up through calculus somewhere and get totally lost when it gets to this weird wibbly-wobbly place where you have to make logical statements using previously unknown Latin notation instead of just solving for x.

Wait, I am missing something here. If the reduction to a true statement is done through operations that can be performed in both direction (which are most of the trivial operations undergrads use) then this is a perfectly fine approach, right?

I have a feeling that the problem is students show "If the equation is true, then 0=0" instead of "Note that 1=1; now, we derive P".

Even if all facts used in the proof are true "in both directions", it's still a serious breach of modern mathematical style to start with what you're trying to prove.

It's also possible that they don't explicitly note that the facts they're using are "true in both directions". edit: to be explicit, in that case I'd still consider the proof wrong

Anyways, if a student presented a proof like that, I would at least take a couple points off for the awkward style unless it was explicitly justified somehow.

It's also kind of a weird proof technique to start with 0=0 or 1=1 and bother to explicitly state this fact...

From reading math research papers, it is not that uncommon to start with what you are trying to prove and proceed with a series of reverisible operations. This is gennerally done to as a first step to convert the proposistion into something that fits more naturally into the proof. This also tends to be done in prose.

It saddens me that so little of what goes in in math papers makes it into textbooks, or math students that do not study original papers themselves.

I don't see any pressing need to freshman to write their very first non-euclidean proofs in the same style as professional mathematicians.

Obviously, it's a matter of style. I still maintain few mathematicians would write canonical discrete math style induction proofs in reverse order.

But then, a mathematician would totally not write out induction proofs the same way we teach in freshman discrete math courses.

So in some sense the style question is completely irrelevant, and what matters is that the student's answer demonstrates unambiguously an understaning of the concept.

Like I said above, induction can be used to prove facts which are not equations. In fact most equations are best proved without induction, at least in my opinion. I was getting this argument even when the fact to be proved was not an equation, it is an affirming the consequent fallacy.

Depends on what you mean by "perfectly fine" ... if the student understands that they deduced the desired conclusion from the true fact 0=0, by a series of steps of the form "our current statement is implied by this next statement, which is implied by the next, which is implied by ... 0=0, which is known to be true", then I guess it's ok other than being an obfuscated/roundabout proof technique.

If the fact to be proved is an equation, then this could be conceivably a reasonable approach - assuming it is correctly written. Our class was a math class, so we weren't just giving them equations that hold for natural numbers (which usually have a more illuminating non-inductive proof anyways).

I can't now remember the specifics of a particular paper because I have seen so many, but the main thing is they believed that if they arrive at some fact that happens to be true then their original hypothesis must be true. It is a classic affirming the consequent fallacy, just shrouded in lots of sophisticated symbol manipulations.

Reply on news.ycombinator.com