# Induction without a base case [duplicate]

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.

-

## marked as duplicate by Ilmari Karonen, hardmath, Sami Ben Romdhane, TMM, Nick PetersonJan 5 '14 at 17:39

It would be better if you included the problem to be inducted on. –  Torsten Hĕrculĕ Cärlemän Jan 5 '14 at 13:32
Also, try looking at backward induction. –  Torsten Hĕrculĕ Cärlemän Jan 5 '14 at 13:32
Any statement which is false for all integers works. –  DanielV Jan 5 '14 at 14:26
All horses are the same colour. –  katrielalex Jan 5 '14 at 16:42
@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 '14 at 17:43

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.

-
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 '14 at 20:15

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

-

(False) 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.

-
This should not be labelled as a theorem. –  Aleš Bizjak Jan 5 '14 at 14:32
@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 '14 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 '14 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?

-

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

-

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.

-
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$$

-

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.

-