Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $m\le n$; this is known as the principle of backwards induction.
We will prove the principle of backwards induction using simple induction. Let $Q(n)$ be the statement that $P(m)$ is true for all natural numbers $m\le n$ if $P(n)$ is true. We need to prove the base case $Q(0)$ and the induction step $Q(n)\implies Q(n++)$.
Base Case
The base case $Q(0)$ is the statement that $P(0)$ is true for all natural numbers $m\le0$ if $P(0)$ is true. Here $m=0$ is only one natural number less than or equal to zero. By assumption $P(0)$ is true, and so the base case $Q(0)$ is true.
Induction Step
We aim to show $Q(n++)$, that $P(m)$ is true for all $m\le n++$ if $P(n++)$ is true. The induction hypothesis is $Q(n)$, that $P(m)$ is true for all $m\le n$ if $P(n)$ is true.
A property of $P$ is that $P(n++)\implies P(n)$, and since $P(n++)$ is true by assumption, then $P(n)$ is true. By the induction hypothesis $P(n)$ is true for all $m\le n$.
In total we have $P(n)$ true for $m\le n$ and $m=n++$. That is, $P(m)$ is true for $m\le n++$. This is $Q(n++)$, and so the induction step is true.
By proving the base case and the induction step, we have proved by simple induction $Q(n)$ is true for all natural numbers $n$. That is, $P(m)$ is true for all $m\le n$ if $P(n)$ is true.
