# Tag Archives: proof

## How to convert a “backwards” proof into a “forwards” proof

Dave Richeson at Division By Zero wrote recently about a “proof technique” for proving equalities or inequalities that is far too common: Starting with the equality to be proven and working backwards to end at a true statement. This is a technique that is almost a valid way to prove things, but it contains — and engenders — serious flaws in logic and the concept of proof that can really get students into trouble later on.

I left a comment there that spells out my  feelings about why this technique is bad. What I wanted to focus on here is something I also mentioned in the comments, which was that it’s so easy to take a “backwards” proof and turn it into a “forwards” one that there’s no reason not to do it.

Take the following problem: Prove that, for all natural numbers $n$,

$1 + 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 1$

This is a standard exercise using mathematical induction. The induction step is trivial; focus on the induction step. Here we assume that $1 + 2 + 2^2 + \cdots + 2^k = 2^{k+1} - 1$ for all natural numbers less than or equal to $k$ and then prove:

$1 + 2 + 2^2 + \cdots + 2^{k+1} = 2^{k+2} - 1$

Here we have to prove two expressions are equal. Here’s what the typical “backwards” proof would look like (click to enlarge):

A student may well come up with this as his/her proof. It’s not a bad initial draft of a proof. Everything we need to make a totally correct proof is here. But the backwards-ness of it — all stemming from the first line, where we have assumed what we are trying to prove — needs fixing. Here’s how.

First, note that all the important and correct mathematical steps are taking place on the left-hand sides of the equations, and the right-hand sides are the problem here. So delete all the right-hand sides of the equals signs and the final equals sign.

Next, since the problem with the original proof was that we started with an “equation” that was not known to be true,  eliminate any step that involved doing something to both sides. That would be line 4 in this proof. This might involve some re-working of the steps, in this case the trivial task of re-introducing a -1 in the final steps:

You could reverse these first two steps — eliminate all “both sides” actions and then get rid of the left-hand sides.

Then, we need to make it look nice. So for n = 1 to the end, move the $(n+1)^\mathrm{st}$ left-hand side and justification to the $n^\mathrm{th}$ right-hand side:

Now we have a correct proof that does not start by assuming the conclusion. It’s shorter, too. Really the main thing wrong with the “backwards” proof is the repeated — and, notice, unnecessary — assertion that everything is equal to the final expression. Remove that assertion and the correct “forwards” proof is basically right there looking at you.

Comments Off on How to convert a “backwards” proof into a “forwards” proof

Filed under Abstract algebra, Geometry, Math, Problem Solving

## Technology in proofs?

We interrupt this blogging hiatus to throw out a question that came up while I was grading today. The item being graded was a homework set in the intro-to-proof course that I teach. One paper brought up two instances of the same issue.

• The student was writing a proof that hinged on arguing that both sin(t) and cos(t) are positive on the interval 0 < t < π/2. The “normal” way to argue this is just to appeal to the unit circle and note that in this interval, you’re remaining in the first quadrant and so both sin(t) and cos(t) are positive. But what the student did was to draw graphs of sin(t) and cos(t) in Maple, using the plot options to restrict the domain; the student then just said something to the effect of “The graph shows that both sin(t) and cos(t) are positive.”
• Another proof was of a proposition claiming that there cannot exist three consecutive natural numbers such that the cube of the largest is equal to the sum of the cubes of the other two. The “normal” way to prove this is by contradiction, assuming that there are three consecutive natural numbers with the stated property. Setting up the equation representing that property leads to a certain third-degree polynomial P(x), and the problem boils down to showing that this polynomial has no roots in the natural numbers. In the contradiction proof, you’d assume P(x) does have a natural number root, and then proceed to plug that root into P(x) and chug until a contradiction is reached. (Often a proof like that would proceed by cases, one case being that the root is even and the other that the root is odd.) The student set up the contradiction correctly and made it to the polynomial. But then, rather than proceeding in cases or making use of some other logical deduction method, the student just used the solver on a graphing calculator to get only one root for the polynomial, that root being something like 4.7702 (clearly non-integer) and so there was the contradiction.

So what the student did was to substitute “normal” methods of proof — meaning, methods of proof that go straight from logic — with machine calculations. Those calculations are convincing and there were no errors made in performing them, and there seemed to be no hidden “gotchas” in what the student did (such as, “That graph looks like it’s positive, but how do you know it’s positive?”). So I gave full credit, but put a note asking the student not to depend on technology when writing (otherwise exemplary) proofs.

But it raises an important question in today’s tech-saturated mathematics curriculum: Just how much technology is acceptable in a mathematical proof? This question has its apotheosis in the controversy surrounding the machine proof of the Four-Color Theorem but I’m finding a central use of (a reliance upon?) technology to be more and more common in undergraduate proof-centered classes. What do you think? (This gives me an opportunity to show off WordPress’ nifty new polling feature.)

## Riemann hypothesis proven?

This paper by Xian-Jin Li at arXiv purports to have proven the Riemann Hypothesis, arguably the most famous of the seven Millenium Problems. It’s just a preprint, of course, so it’s not final (or even peer-reviewed) yet. As commenters in the related Slashdot story mention, articles claiming the proof of the RH show up on arXiv about once per week, so I’m not getting my hopes up. Still, it would be a major breakthrough if it works out.

Filed under Math

## Fear, courage, and place in problem solving

Sorry for the slowdown in posting. It’s been tremendously busy here lately with hosting our annual high school math competition this past weekend and then digging out from midterms.

Today in Modern Algebra, we continued working on proving a theorem that says that if $a$ is a group element and the order of $a$ is $n$, then $a^i = a^j$ if and only if $i \equiv j \ \mathrm{mod} \ n$. In fact, this was the third day we’d spent on this theorem. So far, we had written down the hypothesis and several equivalent forms of the conclusion and I had asked the students what they should do next. Silence. More silence. Finally, I told them to pair off, and please exit the room. Find a quiet spot somewhere else in the building and tell me where you’ll be. Work on the proof for ten minutes and then come back.

As I wandered around from pair to pair I was very surprised to find animated conversations taking place about the proof. It wasn’t because of the time constraint — they’d been at this for three days now. For whatever reason, they were suddenly into it. One pair was practically arguing with each other over the right approach to take. By the end of the 10 minutes, two of the groups had come up with novel and mathematically watertight arguments. Between the two, and with a little bit of patching and a lemma that needs to be proven still, they generated the proof.

One student made the remark that she had been thinking of these ideas all along, but she didn’t feel like it was OK to say anything. This is a very verbal, conversational class done in Moore method style, so I can only interpret that comment to mean that she didn’t feel free enough, or bold enough, to say what she was thinking. The right proof was just bottled up in her mind all this time.

There’s something about our physical surroundings which figures in significantly to our effectiveness as problem solvers. Getting out of the classroom, for this one student at least, was tantamount to giving her permission to have the correct thoughts she was already having and to express them in a proof. I think our problem solving skills are highly inhibited by fear — fear that we will be wrong. And it takes a tremendous amount of confidence and/or courage as a problem solver to overcome that fear.

When you feel that fear in a classroom, it becomes compounded by the dread of looking like an idiot. Changing the surroundings — making things a little less cozy, a little more unusual and uncertain — doesn’t seem to make the fear go away as much as it helps us feel like that fear is perfectly normal and manageable, if not less fearful.