Induction without a base case [duplicate]

$\begingroup$

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.

$\endgroup$ 6

8 Answers

$\begingroup$

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.

$\endgroup$ 1 $\begingroup$

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

$\endgroup$ $\begingroup$

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

$\endgroup$ 3 $\begingroup$

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?

$\endgroup$ $\begingroup$

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

$\endgroup$ $\begingroup$

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.

$\endgroup$ $\begingroup$

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

$\endgroup$ $\begingroup$

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.

$\endgroup$