# “Right” way to get from $P(n)$ to $P(n+1)$ in an inductive step?

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. • I don't get it. They both seem "good". In neither case do you accidentally assume $P(n+1)$. – goblin Apr 8 '16 at 6:27
• @goblin ; I've attached a snippet of the lecture note, hope it clears things up. – Maxis Jaisi Apr 8 '16 at 6:38
• 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. – user113529 Apr 8 '16 at 6:40
• 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. – Gone Jul 3 '16 at 21:55
• @BillDubuque, what is this method called in the literature? – Maxis Jaisi Jul 25 '16 at 5:58

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.

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.

• 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$. – user113529 Apr 8 '16 at 6:34
• @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. – goblin Apr 8 '16 at 6:37
• (cont.) No wonder math seems so illogical! The way its taught, it is illogical. – goblin Apr 8 '16 at 6:38