Induction: In the inductive step, why can't we start with $n$ and go from $n$ to $n + 1$

Question

In actual induction, I know that we are supposed to start with $n+1$ and find $n$ within it, assuming $n$ is true. But I was hoping if anyone could give an explanation or analogy on why we aren't able to start with $n$ and go from $n$ to $n+1$ in the inductive step. Thank you!

Answer 1

'starting with $P(n+1)$ and then finding $P(n)$ wihtin it' is exactly the same as assuming $P(n)$ and deriving $P(n+1)$: it may feel different, but in both cases you show $P(n+1)$ on the basis of $P(n)$

Answer 2

We can start with $n$ and prove it for $n+1$. It turns out that, in order to do that, it is often useful to look what you have proved for $n$ with the statement concerning $n+1$. For instance, if you want to prove by induction that$$(\forall n\in\mathbb N):1+2+3+\cdots+n=\frac{n(n+1)}2,$$in order to prove that, if it holds for $n$, then it holds for $n+1$, you notice that\begin{align}\overbrace{1+2+3+\cdots+n}^{\phantom{n(n+1)/2}=n(n+1)/2}+(n+1)&=\frac{n(n+1)}2+n+1\\&=(n+1)\left(\frac n2+1\right)\\&=(n+1)\times\frac{n+2}2\\&=\frac{(n+1)(n+2)}2.\end{align}So, as you see, I have isolated the $1+2+3+\cdots+n$ from $1+2+3+\cdots+n+(n+1)$ in order to apply the induction hypothesis.

Answer 3

As fleablood comments, you should not be starting with $P(n+1)$ and working your way towards $P(n)$.

The major pitfall here is that you might end up showing that if $P(n+1)$ is true, then $P(n)$ is true, not the other way around. Unless you also show that the steps you took to get to $P(n)$ are reversible, you cannot conclude that $P(n)$ leads to $P(n+1)$.

For this reason, it's much safer to start with $P(n)$ and then manipulate it until you get $P(n)$ instead.

---

Example:

Prove that $n^2\le n$ for all $n\in\mathbb N$.

Clearly this is false, but we will prove it by induction your way.

Trivially the base case holds.

Suppose $n^2\le n$ for some $n=k$. Then we have

\begin{align}&(n+1)^2\le n+1\\\iff{}&n^2+2n+1\le n+1\tag{Expand $(n+1)^2$}\\\iff{}&n^2\le-n\tag{subtract $2n+1$}\\\implies{}&n^2\le n\tag{$-n\le n$}\end{align}

Notice that the last step is not reversible, which is why this proof fails.