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.

  • 2
    $\begingroup$ I think the only one who can really answer that is your professor. $\endgroup$ – Hans Lundmark Oct 28 '18 at 7:55

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.


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)]$.

  • 1
    $\begingroup$ This is not an answer to the question. $\endgroup$ – J.-E. Pin Oct 28 '18 at 7:45

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.