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

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.

• $(n > 1)$....... – Mauro ALLEGRANZA Dec 8 '18 at 18:44
• 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. – Mauro ALLEGRANZA Dec 8 '18 at 19:17

Two possibilities for $$P(n)$$ are

-the assertion that $$n! = 0$$

-the assertion that $$n > 2n$$

• How does $k>2k$ imply $k+1>2(k+1)$? – TonyK Dec 8 '18 at 18:53
• From the base case also $1 > 2$ – Badam Baplan Dec 8 '18 at 18:55
• This is just saying that if $1$ is negative, every 'positive' integer is also negative – Badam Baplan Dec 8 '18 at 18:57
• 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$. – 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 then $$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....