# Mathematical induction (theory)

I've got a question about mathematical induction.

$$\bigg(P(0) \land \big[\forall n\in \mathbb{N},\;\; P(n)\implies P(n+1)\big]\bigg)\implies \forall n\in \mathbb{N}, \; P(n)$$

for the inductive step usually we say

"Let any $$n\in \mathbb{N}$$ and we assume that $$P(n)$$ holds and we will show that P(n+1) holds"

But today I have seen this on an another forum

"We assume there exists $$n$$ such that $$P(n)$$ holds..."

I told them that is formally wrong, because we will prove that $$P(n)\implies P(n+1)$$ only for a specific $$n$$

What is your point of view, Am I right?

Example we want to prove that $$\forall n\ge 1, \quad 2^n>n$$

Induction step ($$\forall n\ge 1,\;\; P(n)\implies P(n+1)$$)

(*) Let any $$n\ge 1$$ and we assume that $$2^n>n$$ holds

$$2^{n+1}>n+1\iff 2^n+2^n>n+1$$ as $$2^n>n$$ and $$2^n>1$$, we conclude that$$2^{n+1}>n+1$$ holds

So we have proved that $$\forall n\ge 1,\;\; P(n)\implies P(n+1)$$ which means $$\forall n\ge 1,\;\; P(1)\implies P(2)\implies \cdots \implies P(n)\implies P(n+1)\cdots$$

It remains the base step because we know noting about $$P(1)$$, $$P(2)$$ and ...

$$P(1) :2^1>1$$ so $$P(1)$$ is true

So we can conclude that $$\forall n\ge 1, \quad 2^n>n$$

If somone says for the induction step (*)

*"We assume there exists $$n\ge 1$$ such that $$2^n>n$$ holds..."*

this "there exists" annoys me

• If you make no special assumption on $n$, then you actually proved that “if $P(n)$ then $P(n+1)$” is true for every $n$. It's just a sloppy way to say “let $n$ be any natural number”. – egreg Sep 27 '18 at 22:07
• my question is, if someone says for the induction step "We assume there exists n such that P(n) holds and we will show that P(n+1) holds" is it wrong or not please? that is my question – Stu Sep 27 '18 at 22:09
• It's a sloppy way to express the usage of induction. Better not using it. I guess you can reformulate that proof in a more rigorous language. – egreg Sep 27 '18 at 22:10
• so that is wrong, thanks – Stu Sep 27 '18 at 22:12
• yes it's what I told them, that is formally wrong to say that!! – Stu Sep 27 '18 at 22:13

After the base case, that is $$\exists n_0$$ such that $$P(n_0)$$ holds, for the induction step we assume as induction hypothesis that for some $$n$$ $$P(n)$$ holds and we need to show that $$P(n) \implies P(n+1)$$.
Note that when we prove the induction step we need to check that $$P(n) \implies P(n+1)$$ holds for $$n\ge n_0$$ otherwise we need to check again the base case.
For example when we prove by induction that $$2^n\ge n^2$$ we have that for the base case $$n=0$$ works but the induction step holds only for $$n\ge 3$$ then we need to prove the base case for $$n\ge 3$$ otherwise the proof by induction is wrong.