#23 on GRE 8767

Question

I am unsure how I would do the work for this question: $S(n)$ is a statement about positive integers $n$ such that whenever $S(k)$ is true, $S(k+1)$ must also be true. Furthermore, there exists some positive integer $n_0$ such that $S(n_0)$ is not true. Of the following, which is the strongest conclusion that can be drawn?

• (A) $S(n_0+1)$ is not true.
• (B) $S(n_0-1)$ is not true.
• (C) $S(n)$ is not true for any $n$ less than or equal to $n_0$
• (D) $S(n)$ is not true for any $n$ greater that or equal to $n_0$
• (E) $S(n)$ is not true for any $n$.

I know that the answer is C. I am just unsure how to get to that conclusion.

Answer 1

If you know that $S(n_0)$ is false, then you also know that $S(n_0-1)$ is false. (Because, if $S(n_0-1)$ were true, then $S(n_0)$ would have to be true, which we know it isn't.

By the same reasoning, since we know that $S(n_0-1)$ is false, we know that $S(n_0-2)$ is false. And in the same way that $S(n_0-3)$ is false and so on for all integers less than or equal to $n_0$.

This is of course a stronger claim than (b) and we don't know about the truth or falsehood of (a), (d) or (e).

Answer 2

S cannot be true for any $n\le n_0$.

Suppose, there is an $n \le n_0$ , such that S(n) is true. So, by the property S(n) true -> S(n+1) true (induction) , S(n) is true for all numbers $\ge n$. So, S($n_0$) is true, contradicting our assumption.

For the numbers n>$n_0$ , S(n) is not determined. We can only say : If there is some number k, such that S(k) is true, then S(n) is true for all $n\ge k$. But there maybe no such k.

Answer 3

Hint $\ $ If $\,S\,$ is not always false, let $\,n_1$ be least such that $\,S(n_1)\,$ is true. Then $\,S(n)\,$ is false for $\,n < n_1,\,$ and true for $\,n\ge n_1$ by induction, since $\,S(k)\,$ true $\,\Rightarrow\, S(k+1)\,$ true. You are given only that $\,S(n_0)\,$ is false, i.e. $\,n_0 < n_1.$ Using the above characterization (initial segment / interval having all false values, followed by a terminal segment of all true values), it is easy to evaluate the truth of the five cases.