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

489 Views Asked by At

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

2

There are 2 best solutions below

0
On BEST ANSWER

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.

3
On

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.