= Solution
The <primitive recursive functions> are the smallest collection containing zero functions, successor $S(n)=n+1$, and coordinate projections, and closed under composition and <primitive recursion>. The recursion scheme forms $F$ from already constructed functions $G,H$ by
$$
F(\mathbf x,0)=G(\mathbf x),\qquad
F(\mathbf x,n+1)=H(\mathbf x,n,F(\mathbf x,n)).
$$
Constants follow by composing successor with zero. Define addition, multiplication and exponentiation successively by
$$
A(m,0)=m,\quad A(m,n+1)=S(A(m,n)),
$$
$$
M(m,0)=0,\quad M(m,n+1)=A(M(m,n),m),
$$
$$
E(m,0)=1,\quad E(m,n+1)=M(E(m,n),m).
$$
At each stage the initial and step functions are compositions of <primitive recursive functions> already available. Induction on $n$ gives $A(m,n)=m+n$, $M(m,n)=mn$, and $E(m,n)=m^n$, with the recursive convention $0^0=1$. Composition with the second projection now gives
$$
\boxed{f(m,n)=A(E(m,n),n)=m^n+n\text{ is primitive recursive}.}
$$
Back to article page
