Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

I am looking for an example where you have $P(n)$ implying $P(n+1)$. However there is no base case. For which there is therefore no solution at all for the induction problem even though the inductive step itself works.

share|improve this question

marked as duplicate by Ilmari Karonen, hardmath, Sami Ben Romdhane, TMM, Nicholas R. Peterson Jan 5 at 17:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
It would be better if you included the problem to be inducted on. –  Torsten Hĕrculĕ Cärlemän Jan 5 at 13:32
    
Also, try looking at backward induction. –  Torsten Hĕrculĕ Cärlemän Jan 5 at 13:32
1  
Any statement which is false for all integers works. –  DanielV Jan 5 at 14:26
4  
All horses are the same colour. –  katrielalex Jan 5 at 16:42
3  
@katrielalex: That comes to mind, but is not an example. The base case (one horse) works, but the first instance of the induction step fails. –  Marc van Leeuwen Jan 5 at 17:43

8 Answers 8

up vote 36 down vote accepted

Suppose we want to prove $n=n+1$ for all (positive) integers $n$. We omit the base case. The induction hypothesis is $k=k+1$ for some $k\in \mathbb N$. Adding $1$ to both sides gives $k+1=k+1+1$, or $(k+1)=(k+1)+1$, which is the statement to be proven for $n=k+1$. Thus, we have completed the induction step, but there is no base for which this is true, so the statement won't have to be true too.

share|improve this answer
1  
Just realise, if $P(k)$ is true, i.e. $k=k+1$, then $P(k+1)=P(k)=$true. Even induction itself get messed up... –  peterwhy Jan 5 at 20:15

$$1+2+3+\dots+n=\frac{n(n+1)}2+\pi$$ $$1+2+4+\dots+2^{n-1}=2^n$$

share|improve this answer

Theorem. Let $P$ be literally any property of elements of $\mathbb N$. Then every element of $\mathbb N$ has property $P$.
Proof. This is true if all nonempty finite subsets of $\mathbb N$ consist of elements with property $P$. Suppose $n\ge 1$ and all elements of subsets of $\mathbb N$ with $n$ elements satisfy $P$. Let $S\subset\mathbb N$ have $n+1$ elements, and pick any $x\in S$. Since $S'=S\setminus\{x\}$ has $n$ elements, all members of $S'$ satisfy $P$. Moreover, since $n=|S'|>0$ there exists $y\in S'$. Then $(S'\setminus\{y\})\cup\{x\}$ has $n$ elements, so $x$ has property $P$ as well. q.e.d.

share|improve this answer
    
This should not be labelled as a theorem. –  Aleš Bizjak Jan 5 at 14:32
1  
@AlešBizjak Did you, for a second, think it is true? My point being, the only reason why I shouldn't call it a theorem is that it would potentially mislead readers. –  Karl Kronenfeld Jan 5 at 15:44
    
No, I didn't think it was true and that is my point. Statements that are not true should not be called "Theorem" in a serious answer, especially since the question is about statements which are not true. –  Aleš Bizjak Jan 5 at 16:07

Let $P(n)$ be the statement "$1=2$". Assume $P(k)$ is true, hence $1=2$. By assumption, $1=2$, so $P(k+1)$ is true.

Then what?

share|improve this answer

Simply let $P(n)$ be the statement that $n=n+1$. Suppose this is true for some positive integer $k$. Then $k=k+1$, so $k+1=k+1+1$, and we also have $P(k+1)$.

share|improve this answer

Let $P(n)$ be a false statement, for each $n$. Then $P(k) \implies P(k+1)$ vacuously, because a false statement implies any other, but certainly $P(0)$ is false.

share|improve this answer
  1. Suppose we want to show $n=n+1$ where $n\in \mathbb{N}$. Now suppose the statement holds for some $n$ $$n=n+1$$ then we want to show $$n+1=n+1+1$$ which is easily true since $(n+1)+1=n+1$.

  2. Suppose we want to show for all $n\in \mathbb{N}^+$, $n+1<n$. Now suppose the statement holds for some $n$ $$n+1<n$$ then $$n+1+1=(n+1)+1<n+1$$

share|improve this answer

Let $P(n)$ be the statement "$2^{\aleph_0}=n+\aleph_1$"(Continuum Hypothesis). The inductive step itself works but it gives nothing. We are not able to check (in the theory $ZFC$) the statement $P(0)$ is false or true.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.