2
$\begingroup$

I'm reading a Math lecture note on mathematical induction, and in it, the author condemns a way of concluding that $\ P(n) \implies P(n+1)\ $, which is done by assuming $\ P(n+1)$, making a few deductions, and arriving at a $ \mathtt{True}\ $ statement. I'll give a very elementary example of proving an identity involving the sum of natural numbers.

Proof [Good]: Clearly, $n = 1$ works. Suppose the identity holds for $n$. Then adding $n+1$ to both sides of the identity, we get $ 1+2+\ ... \ +n+(n+1) = \frac{n(n+1)}{2}+\frac{2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$. Thus $P(n) \implies P(n+1)$, which closes the induction.

Proof [Bad?]: $n=1$ works. Suppose the identity holds for $n$. Then we want to prove that $1+2+\ ... \ +n+(n+1) = \frac{(n+1)(n+2)}{2}$. Note that by our induction hypothesis, the $\mathsf{LHS}$ can be re-written as $\frac{n(n+1)}{2}+(n+1) = \frac{(n+1)(n+2)}{2}$, which equals the $\mathsf{RHS}$, which means that $P(n) \implies P(n+1)$, and we're done.

The author of the lecture note objects to [Bad?] because we're assuming what we wanted to prove, which is circular. However, I've seen a lot of induction proofs which are in the form of [Bad?], even in famous Math books. One example is an induction argument used to prove a very elementary fact about natural numbers, which I'll paraphrase from Terry Tao's Analysis I book:

Theorem: For any natural number $n$, $n+0 = n$. Proof: Clearly $n = 0$ works. Assume that $n+0 = n$, for any natural $n$. We wish to show that $\ S(n)+0 = S(n)\ $ (here $\ S(n)$ denotes the successor of $n$). Note that $\ S(n)+0 = S(n+0) = S(n)$, which means that $S(n) = S(n)$, and we're done.

In fact, inductive proofs in the form above are used many times in Terry Tao's book. Is there anything wrong with such proofs?

Edit: In case I wasn't clear, here's a snippet of the lecture note.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ I don't get it. They both seem "good". In neither case do you accidentally assume $P(n+1)$. $\endgroup$ – goblin Apr 8 '16 at 6:27
  • $\begingroup$ @goblin ; I've attached a snippet of the lecture note, hope it clears things up. $\endgroup$ – Maxis Jaisi Apr 8 '16 at 6:38
  • $\begingroup$ As long as all the statements are if and only if, everything is fine. The example you attached, $27232=323$ doesn't work because its a one way implication. $\endgroup$ – user113529 Apr 8 '16 at 6:40
  • $\begingroup$ See this answer for a better presentation of the telescopic sum induction method deemed "bad". Telescopy is a very powerful technique for inductive problems of this form. $\endgroup$ – Gone Jul 3 '16 at 21:55
  • $\begingroup$ @BillDubuque, what is this method called in the literature? $\endgroup$ – Maxis Jaisi Jul 25 '16 at 5:58
2
$\begingroup$

We are not assuming what we want to prove. The key point is that the "bad" author uses equivalence transforms to arrive at a true (based on the induction hypothesis) statement. It is just unfortunate that the fact that the transforms are equivalence transforms ("$\iff$ instead of - insufficiently and wrongly - just "$\implies$") is hidden from the reader in the word "re-written". So, while not wrong per se, the "bad" proof at least suffers from the potential to stylistic improvement in this respect.

Apart from this, the author has a point: Whenever you apply transforms to arrive at a true statement from the statement you want to prove, there is always the risk that somewhere deep inside you accidentally have a step that is only $\implies$ and not $\iff$ ... So while this direction may be very well suitable for discovering a proof on scratch paper, I'd still recommend to rewrite everything into the "good" order for a published proof.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

As I understand it, an invalid 'proof' involves an inferential strategy like:

$$P(n+1) \Rightarrow \cdots \Rightarrow \cdots \Rightarrow \mathrm{True}$$

which fails to establish the truth of $P(n+1)$.

A genuine proof looks more like

$$P(n+1) \Leftrightarrow \cdots \Leftrightarrow \cdots \Leftrightarrow \mathrm{True}$$

or

$$\mathrm{True} \Rightarrow \cdots \Rightarrow \cdots \Rightarrow P(n+1),$$

both of which succesfully establish the truth of $P(n+1)$. But this has nothing to do with proof by induction per se; its just basic logic.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think the author is probably concerned about the invalid proof $P(n+1)\Rightarrow True$, but as long as you word [Bad?] correctly, then your really saying $P(n+1)\Leftrightarrow True$. $\endgroup$ – user113529 Apr 8 '16 at 6:34
  • $\begingroup$ @user43687, yep, I agree completely. High school students (and teachers!) frequently write almost-correct solutions to problems for exactly this reason. They assume $3x+1=4$ and deduce $x=1$, but never pause to check that from $x=1$, you can deduce $3x+1=4$. If pressed, the teachers sometimes appeal to a high powered theorem asserting that $3x+1=4$ has precisely one solution, so that the converse follows immediately. My only issue with this is they expect the students to intuitively understand and know this high-powered theorem, and never bother to explain it or make their logic explicit. $\endgroup$ – goblin Apr 8 '16 at 6:37
  • 1
    $\begingroup$ (cont.) No wonder math seems so illogical! The way its taught, it is illogical. $\endgroup$ – goblin Apr 8 '16 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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