# Backwards Induction

## Theorem

Let $\map P n$ be a propositional function depending on $n \in \N$.

Suppose that:

- $(1): \quad \forall n \in \N: \map P {2^n}$ holds.
- $(2): \quad \map P n \implies \map P {n - 1}$.

Then $\map P n$ holds for all $\forall n \in \N$.

The proof technique based on this result is called **backwards induction**.

## Proof

Aiming for a contradiction, suppose $\exists k \in \N$ such that $\map P k$ is false.

From Power of Real Number greater than One is Unbounded Above, $\set {2^n: n \in \N}$ is unbounded above

Therefore we can find:

- $M = 2^N > k$

Now let us create the set:

- $S = \set {n \in \N: n < M, \map P n \text { is false} }$

As $k < M$ and $\map P k$ is false, $S \ne \O$ and as $\forall x \in S: x < M$ it follows that $S$ is bounded above.

So from Set of Integers Bounded Above by Integer has Greatest Element, $S$ has a greatest element.

However, $\map P n$ holds for $m < n \le M$ and hence $\map P {m + 1}$ holds.

But $\map P {m + 1} \implies \map P m$ and so $\map P m$ holds after all.

So there can be no such $m$ and therefore $S = \O$, hence there can be no such $k \in \N$ such that $\map P k$ is false.

Hence the result.

$\blacksquare$

## Sources

- 1977: K.G. Binmore:
*Mathematical Analysis: A Straightforward Approach*... (previous) ... (next): $\S 3$: Natural Numbers: Exercise $\S 3.11 \ (5)$