Induction: Using P(n) vs P(n+1) is bad style?

Question

I'm in a proofs class and we were discussing induction. One of the most common ways we (the students) had seen induction was to represent "Statement P hold for $n$" by $P(n)$. Thus, we take the inductive hypothesis of assuming $P(n)$ is true and turning attention to $P(n+1)$. Of this format, my professor said "It's not really the best style and we won't use it that often".

Why would he say that? I've only ever (previously) seen induction in that format and he didn't really explain what he meant.

Answer 1

In real life, you'll be explicit about what $P$ is, and you won't abbreviate it.

To prove that all naturals are greater than or equal to $0$, we proceed by induction. The base case is trivial: $0 \leq 0$ because $0 = 0$. Now, suppose $0 \leq n$. We have $n < n+1$ because [whatever reason - e.g:] there exists a nonzero natural we can add to $n$ to make $n+1$ - namely $1$. Therefore we also have $n \leq n+1$. Then $$\underbrace{0 \leq n}_{\text{inductive hypothesis}} \leq n+1$$ and so by transitivity $0 \leq n+1$, which completes the proof.

No $P$'s required. In general you want your proofs to look like prose unless you're being really formal; only use symbols if they actually make things clearer.

Answer 2

Hint: The general proof is like this:

Induction base: $P(0)$.

Induction step: $\forall n\geq 0 [ P(0)\wedge P(1)\wedge \ldots \wedge P(n)\Rightarrow P(n+1)]$.

Then we have proved $\forall n\geq 0[P(n)]$. Why? Consider modus ponens.

For most assertions, the induction step is simpler:

$\forall n\geq 0 [P(n)\Rightarrow P(n+1)]$.