        \problemdata       % Takes 5 *mandatory* arguments
        {natural-pred}             % latex-friendly label for the prob.
        {predicates}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 tut2-1} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
Suppose $S(n)$ is a predicate on natural numbers, $n$, and
suppose
\[
\forall k \in \nats\; S(k) \implies S(k+2).
\]
Explain which of the following is possible:
\begin{problemparts}
\problempart $\forall n \ge 0\; S(n)$
\problempart $\bar{S(0)} \land \forall n \ge 1\; S(n)$
\problempart $\forall n \ge 0\; \bar{S(n)}$
\problempart $(\forall n \le 100\; S(n)) \land (\forall n > 100\; \bar{S(n)})$
\problempart $(\forall n \le 100\; \bar{S(n)}) \land (\forall n > 100\; S(n))$
\end{problemparts}

\solution{
\begin{enumerate}

\item The formula in this case specifies that $S$ is always true.  So
$S(k+2)$ is always true, and therefore $S(k) \implies S(k+2)$ is always
true.  So this case is possible.

\item This time $S$ is false at 0, but true everywhere else.  So $S(k)
\implies S(k+2)$ still always holds because $S(k+2)$ is still always true.
So this case is possible.

\item Now $S$ is always false.  So $S(k) \implies S(k+2)$ is always true
because $S(k)$ is false.  So this case is possible.

\item In this case, $S$ is true for $n$ up to 100 and false from 101 on.
So $S(99)$ is true, but $S(101)$ is false.  That means that $S(k) \not
\implies S(k+2)$ for $k = 99$.  This case is impossible.

\item In this final case, $S$ is false for $n$ up to 100 and true from 101
on.  So $S(k) \implies S(k+2)$ for $k \le 100$ because $S(k)$ is false,
and $S(k) \implies S(k+2)$ for $k \ge 99$ because $S(k+2)$ is true.  So
this case is possible.

\end{enumerate} 
}

\end{problem}
