0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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”. $\endgroup$ – egreg Sep 27 '18 at 22:07
  • $\begingroup$ 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 $\endgroup$ – Stu Sep 27 '18 at 22:09
  • $\begingroup$ 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. $\endgroup$ – egreg Sep 27 '18 at 22:10
  • $\begingroup$ so that is wrong, thanks $\endgroup$ – Stu Sep 27 '18 at 22:12
  • $\begingroup$ yes it's what I told them, that is formally wrong to say that!! $\endgroup$ – Stu Sep 27 '18 at 22:13
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Aloizio Macedo Sep 28 '18 at 1:03
  • $\begingroup$ @AloizioMacedo You are right sorry for that, even if our comments were completely inherent to the object raised by the OP. I would have deleted that after a while. Thanks $\endgroup$ – gimusi Sep 28 '18 at 1:16

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.