Give an example of an assertion which is not true for any positive integer, yet for which the induction step holds.

First of all, definition.

In inductive step, we suppose that $P(k)$ is true for some positive integer $k$ and then we prove that $P(k + 1)$ is true.

My thoughts : Since the assertion has to satisfy the induction step, it must be false for $n=1$.

But I cannot think of any such assertion. Does anyone have any hints? Thank you.

Edit: Just realised that my thoughts don't make much sense, as the question demands the assertion to be false for every positive integer.

  • $\begingroup$ $(n > 1)$....... $\endgroup$ – Mauro ALLEGRANZA Dec 8 '18 at 18:44
  • $\begingroup$ Let $P(n) := (n > 1)$. Clearly $(n > 1) \to ((n+1) > 1)$ holds (because $\text F \to \text F$ is $\text T$) and thus we have that $\forall n (P(n) \to P(n+1))$ is true. But $P(1)$ is not. $\endgroup$ – Mauro ALLEGRANZA Dec 8 '18 at 19:17

There is no shortage of good answers to this question, so I'll give a couple examples in the hopes that thinking about them will help you to produce your own answers.

Two possibilities for $P(n)$ are

-the assertion that $n! = 0$

-the assertion that $n > 2n$

  • $\begingroup$ How does $k>2k$ imply $k+1>2(k+1)$? $\endgroup$ – TonyK Dec 8 '18 at 18:53
  • $\begingroup$ From the base case also $1 > 2$ $\endgroup$ – Badam Baplan Dec 8 '18 at 18:55
  • $\begingroup$ This is just saying that if $1$ is negative, every 'positive' integer is also negative $\endgroup$ – Badam Baplan Dec 8 '18 at 18:57
  • $\begingroup$ Strong induction. $k > 2k$ and $1 > 2$ so $k+1 > 2k + 2 = 2(k+1)$. Also by strong induction. $n=0$. So $n+1 = n + 0 = n = 0$. $\endgroup$ – fleablood Dec 8 '18 at 19:07

$P(k):k$ is irrational

$P(k): \{k\}>0$, where $\{k\}$ denotes the fractional part of $k$


$n < n$ does not hold for any $n$ but the inductive step holds:

If $k <k$ then $k+1<k+1$


It's easier than you think:

$n \le n-2$

Then $n+1 \le (n-2) + 1 = n-1 = (n+1) -2$.

$n$ is not an integer.

$n + 1$ is not an integer.

$n$ is infinite.

If $n+1$ were finite then $n = (n+1) - 1=n$ would be finite which is a contradiction.

$n = n-1= 6$

$n+1 = (n-1)+1 = n = n-1 = 6$

and so on....


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.