Shaun, when you say "we substituted $n+1$ for all $n$ in the equation", that's not quite right. First, you need to be careful about "the equation" you are talking about. In the inductive step in this problem, you *assume* that "the equation" is true for a *fixed* $n$, but *just that one $n$*, not all of them. You are trying to show that the equation is true *for all natural numbers*.

Here is an analogy. You are trying to prove that there is a ladder that starts with a bottom rung and continues up infinitely many rungs. In the base case, you show that there is a bottom rung of the ladder. In the inductive step, you assume that there is a single rung of the ladder *somewhere* up the ladder and then do some yoga to show that there is a rung just above that one. If you can pull this off, then the PMI says, "well done, you've got yourself a whole ladder."

Substituting $n+1$ for $n$ isn't allowed in the inductive step because $n$ is fixed (and you are assuming the equation holds for that $n$) and you don't yet know it works for $n+1$; that's what you are trying to prove. So, you start with *one side* of the thing you are trying to prove, beat it around doing legal stuff, and then, hopefully, arrive at the other side of what you were trying to prove. The big picture is that when you are trying to beat it around doing legal stuff, you should be aiming to use the inductive hypothesis, i.e., the statement you assumed is true involving $n$.

I need to be picky about something Jess said. She wrote:

When you start the induction step, you want to include where lives, and assume what you are trying to prove.

Now, I'm pretty sure I know what Jess *meant*, but hopefully everyone realizes that assuming what you are trying to prove is bad. When you do this the universe implodes.

The whole reason that I usually introduce $k$ on the inductive step is to avoid some of this confusion between $n$ being fixed versus a variable.