Backwards Induction

Theorem

Let $P \left({n}\right)$ be a propositional function depending on $n \in \N$.

Suppose that:

• $\forall n \in \N: P \left({2^n}\right)$ holds.
• $P \left({n}\right) \implies P \left({n-1}\right)$.

Then $P \left({n}\right)$ holds for all $\forall n \in \N$.

Proof

Suppose $\exists k \in \N$ such that $P \left({k}\right)$ is false.

Since $\left\{{2^n: n \in \N}\right\}$ is unbounded above by Boundedness of Nth Powers‎, we can find $M = 2^N > k$.

Now let us create the set $S = \left\{{n \in \N: n < M, P \left({n}\right) \mbox{ is false}}\right\}$.

As $k < M$ and $P \left({k}\right)$ is false, $S \ne \varnothing$ and as $\forall x \in S: x < M$ it follows that $S$ is bounded above.

So from Integers Bounded Above has Maximal Element, $S$ has a maximal element.

However, $P \left({n}\right)$ holds for $m < n \le M$ and hence $P \left({m+1}\right)$ holds.

But $P \left({m+1}\right) \implies P \left({m}\right)$ and so $P \left({m}\right)$ holds after all.

So there can be no such $m$ and therefore $S = \varnothing$, hence there can be no such $k \in \N$ such that $P \left({k}\right)$ is false.

Hence the result.

$\blacksquare$

Sources

• K.G. Binmore: Mathematical Analysis: A Straightforward Approach (1977)... (previous)... (next): $\S 3.11 \ (5)$