Inductive step for mathematical induction

Question

For the inductive step in mathematical induction, which of the following is correct?

“$P_k$ is true” $\implies$ “$P_{k+1}$ is true”

or

“$P_k\implies P_{k+1}$” is true

Is there a difference in the two statements above?

Answer 1

There is no difference. Note that the implication does not state the antecedent is in fact true, nor does it state the consequent is in fact true. It is simply saying that IF the antecedent were true, THEN the consequent would also be true.

This makes sense when you consider how a proof by induction is performed. The inductive step begins with assuming that $P(k)$ is true. You then attempt to validly deduce $P(k+1)$. If you can, then you are justified in stating $P(k) \rightarrow P(k+1)$, meaning "if $P(k)$ is true, then $P(k+1)$ is true," or in other words, the $P(k+1)$ is true under the assumption that $P(k)$ is true. It is only when the antecedent is in fact true that the truthfulness of consequent is implied, which is why a proof by induction includes a basis step. The basis step provides the first instance for which the antecedent is true, which implies that your propositional function is true for the very next element. That, in turn, becomes the basis for implying the truthfulness of the propositional function for the next element after that, and so on, and so on...