Inverted induction

I am working on a proof, and to do it, I think it would be optimally to use induction backwards.

Show that 1 doesn't work. Assume n doesn't work. Prove that n+1 doesn't work.

Is this valid?

Solution 1:

What you are describing is still a proof by induction. A proof by induction is:

• Take a statement $P(n)$ about integers.
• Prove $P(1)$
• Prove $\forall n:P(n) \implies P(n+1)$

What you are doing is:

• Take a statement $A(n)$
• Prove $\neg A(1)$
• Prove $\forall n: \neg A(n)\implies \neg A(n+1)$

So what you are doing si simply performing induction on the statement $\neg A$, i.e., you are performing standard induction, but your statement $P$ is actually a negation of some other statement. It is still a statement, so there is nothing truly "inverted" happening.

Solution 2:

Indeed, it can be viewed as "inverted" induction, i.e. as a special case of Fermat's method of infinite descent, since the contrapositive of your induction step is: $\ n$ works $\,\Rightarrow\, n\!-\!1\,$ works. This descent form of induction is a very natural way to present many inductive proofs.