Proof of the principle of backwards induction

Proof: Let $n \in \mathbb{N}$. Using induction on $n$, for the base case $n = 0$, we need to show that $P(m)$ is true $\forall\ m\le 0$. But only $0\le 0$ so we just need to show that $P(0)$ is true. Since $P(n)$ is true from the hypothesis, $P(0)$ is true and that completes the base case.

Suppose inductively that the principle if true for $n$, i.e $P$ is such that $P(n)$ is true, and whenever $P(m{+\!+})$ is true, $P(m)$ is true $\forall m\le n$. We have to show the principle is true for $n{+\!+}$ i.e we need to show that $P(m)$ is true $\forall\ m\le n{+\!+}$ given that $P(n{+\!+})$ is true and given that whenever $P(m{+\!+})$ is true, $P(m)$ is true.

Since $P(n{+\!+})$ is true, then $P(n)$ is also true. So we have to show that $P(m)$ is true $m<n$. But from the inductive hypothesis, $P(m)$ is true $\forall$ $m\le n$ and that completes the induction. $\square$

Prove, by ordinary induction on $k$, the statement "if $n-k\geq0$ then $P(n-k)$. The base case is $P(n)$, and the induction step, going from $k$ to $k+1$, comes from the "backward induction" hypothesis, because increasing $k$ decreases $n-k$.

This answer is to show the statement can be proved on (upward) induction on $n$, as in the hint.

Suppose the statement holds at a specific $n$. The statement of it for $n{+\!+}$ is then:

Suppose $P(n{+\!+})$ is true, then it follows that $P(m)$ holds for all $m \le n{+\!+}.$

From the assumption that $P(n{+\!+}) \implies P(n),$ we arrive at $P(n)$ true, so that from the inductive hypothesis $P(k)$ holds for all $k \le n$. Together with the assumption that $P(n{+\!+})$ holds, we have the desired conclusion of the inductive step, i.e. that $P(m)$ holds for all $m \le n{+\!+}.$