EDB — 27N

Recall that $S(f_h(n))=f_h(S(n))$ by recursive definition; Consider

$P(0)$ is the clause

which is true because it is the initial value of the recursive definition $f_{S(h)}$ and $f_h$. For the inductive step we assume that $P(n)$ is true and we study $P(S(n))$, within which we can say

where in (1) we used the recursive definition of $f_h$ with $S(h)$ instead $h$, in (2) we used the inductive hypothesis, and in (3) we used the recursive definition of $f_h$. This completes the inductive step.

(Note, in the first step, how important it is that in the definition of $P(n)$ there is $\forall h\in \mathbb{N},\dots$).