Why do we switch variables in strong induction?

Question

I'm in an introduction to proofs class and during our discussion of strong induction the professor kept telling us to switch our variables. Why is this? Why, when proving a statement P(n), would it make sense to prove P(k) $\forall k \in\mathbb{N}$, such that k < n, and then show that P(k) $\implies$ P(n+1), instead of just showing P(n) for n < n+1?

Answer 1

Your account of what the professor said seems to be a bit garbled. But that may be the topic of a different question: what is proved vs. what is assumed in each part of an inductive proof, and how to make your use of $<$ vs. $\leq$ and $n$ vs. $n+1$ consistent.

The whole point of using a notation like $P(n)$ is that you can put different things inside the parentheses: $P(1),$ $P(2),$ $P(n+1),$ or $P(k).$ Now in strong induction we want to prove the inductive step for an arbitrary number $n,$ and we say something about every number less than $n.$ So what name shall we use to represent "every number less than $n$"? We can't re-use the name $n$ for this variable: that would say $n < n,$ a contradiction.