Induction - how to prove like $s(n) \Rightarrow s(n-1)$

Question

Until now it was all ok for proving the statements like

$S(n) \Rightarrow S(n+1)$, however I've encountered a question that says:

Let $S(n)$ be an open statement such that

• $S(n)$ is true for infinitely many natural numbers $n$.
• $s(n) \Rightarrow s(n-1)$ for $n > 1$.

Prove that $S(n)$ is true for all $n\ge 1$.

I couldn't figure out the solution of this type of questions.

Thank you for your effort in advance!

Answer 1

Choose a random $n\in\mathbb{N}$. Suppose that $S(n)$ is not true, then this implies that $S(m)$ is not true for any $m>n$, since $S(n)$ being true implies $S(n-1)$ being true. However, if $S(m)$ is not true for any $m>n$, then there can only be finitely many statements true, namely $n-1$, which is a contradiction.

Answer 2

You can show with induction that if $k \leq n$, then $S(n) \Rightarrow S(k)$. But given any $k\in \mathbb N$, there exists some $n \geq k$ such that $S(n)$ is true, since $S(n)$ is true for infinitely many natural numbers.

Answer 3

By contraposition, the second premise, $\;\forall n \in \{2;\infty\}: (S(n) \to S(n-1))\;$, is equivalent to :$$\forall n \in \Bbb \{1;\infty\}:(\neg S(n)\to \neg S(n+1))$$

Hence if there is any natural number (greater than $0$) that does not satisfy the predicate, $S$, then by induction we could prove that no greater natural number would satisfy the predicate.   This would mean there were only finite many natural numbers that could satisfy the predicate, which contradicts the first premise.   Therefore there cannot be any such number which does not satisfy the predicate.   Meaning that all of them do so.

$$\therefore \forall n \in \{1;\infty\} : S(n)$$