Whats an example of a predicate where if $P(1)$ is False, and $(\forall k\geq 1)(P(k)\implies P(k+1))$ is True for all natural numbers

Question

The textbook solution just says that there is a predicate which satisfies those conditions. Wouldn't this be false since if the base case doesn't hold then by induction principle its false? Is there an example where $P(1)$ is False, and $(\forall k\geq 1)(P(k)\implies P(k+1))$ is True?

score 2 · Accepted Answer · answered Jun 12 '19 at 06:23

2

Try $$k>42$$ or try $$ k^3-k+1 \text{ is a multiple of }3$$ or try $$ \text{There exists an even $m$ with $2<m<k$ that is not the sum of two primes}.$$

answered Jun 12 '19 at 06:23

Hagen von Eitzen

374,180

score 1 · Answer 2 · answered Jun 12 '19 at 06:26

1

You could try $n\gt n$ or $n=n+1$ which are false for all $n$.

The point is that you need the base case to found the induction. Otherwise you can prove anything (ie all the consequences of a false statement)

answered Jun 12 '19 at 06:26

Mark Bennet

100,194

Whats an example of a predicate where if $P(1)$ is False, and $(\forall k\geq 1)(P(k)\implies P(k+1))$ is True for all natural numbers

2 Answers2