Discrete Math, Strong induction. choosing between showing 'k' or k+1'

Question

For the induction step of the proof, why are the first and third example just trying to 'show' $k$ in the "We want to show that.." line of the proof, and in the other example we are trying to show $k+1$ instead?

Answer 1

Consider that in (B) of the above, $...m<k$ then $P(k)$. The 'show' part of your question is dealing with the then P(k) part of (B). In your second example, where $k+1$ is being used, you are previously stating (in your induction hypothesis) that $m <= k$ and since $k$ is now included in the range of the induction hypothesis (due to the equl part of less than or equal), you also need to change the then part to reflect, and you are therefore now trying to show then $P(K+1)$.

If you were to just show $P(K)$ in your second example then you would be just be showing part of the antecedent of your conditional (If part) instead of the consequent (then part).

In the other two examples, the I.H. has the range $m<k$ which isn't the same as $m <= k$ which allows to use (B) above without manipulation so in those two cases you are trying to show $P(k)$.

Someone correct me if I'm wrong.