Proof of the principle of backwards induction I have difficulty in neatly writing down a proof for the following from Terence Tao's Analysis I, where $m{+\!+}$ is the successor function:

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\leq n$; this is know as the principle of backwards induction. (Hint: apply induction to the variable $n$.)

First of all, I am unsure about what the base case should look like. For the induction step, I understand that if we suppose inductively that $P(n)$ is true, that then for a natural number $a$ s.t. $a{+\!+}=n$ it holds that $P(a)$ is true, and then for a natural number $b$ s.t. $b{+\!+}=a$ it holds that $P(b)$ is true etc. Hence for all natural numbers $m\leq n$, $P(m)$ is true.
Could anyone please tell me what the base case should look like, and whether there is a neater way of writing down the induction step?
 A: 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$
A: 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$.
A: 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{+\!+}.$
A: Same answer as @coffeemath but made more clear. The statement to be proved is this:
$\forall n\in \textbf{N}, \Bigg (P(n) \implies (\forall m \le n, P(m)) \Bigg )$
which we can rewrite as, taking $R(n) := (\forall m \le n, P(m))$
$\forall n\in \textbf{N}, \Bigg (P(n) \implies R(n) \Bigg )$
Define $Q(n):=(P(n) \implies R(n) )$. We want to show $\forall n\in \textbf{N}, Q(n)$ and we shall use the principle of mathematical induction on $Q(n)$.
Step 1: $Q(0):=(P(0) \implies R(0) )\equiv (P(0) \implies P(0) )$. Thus, Q(0) is true.
Step 2: Assume $Q(n)$ is true.
Step 3: Since $P(n{+\!+})\implies P(n)$ and $P(n) \implies R(n)$, we have $P(n{+\!+}) \implies R(n)$. (syllogism). Now $ (P(n{+\!+}) \implies R(n)) \equiv (P(n{+\!+}) \implies R(n)) \land P(n{+\!+})) \equiv (P(n{+\!+}) \implies R(n{+\!+})) \equiv Q(n{+\!+})$.
Hence $Q(n)$ is true $\forall n$. QED.
