Recursive relation using successor function What is the recursive relation for $$H(m)=2^{(m^2)}$$ using successor function recursive relation for multiplication: $$mult(x,0)=0; mult(x,S(y))=add(x,mult(x,y))$$ recursive relation for addition: $$add(x,0)=x; add(x,S(y))=S(add(x,y))$$ Where H function is a composite function. I need to come up with recursive relation for that function. What steps do you suggest I take? Thanks so much in advance!!!
 A: Define the exponential $\mathit{exp}(m, n)$ in the absolutely standard way:

$\mathit{exp}(m, 0) = 1$,
$\mathit{exp}(m, Sn) = \mathit{mult}(\mathit{exp}(m, n), m)$. 

That shows $\mathit{exp}$ is p.r. And now put 

$H(m) = \mathit{exp}(2, \mathit{mult}(m, m))$.

Then $H$ is p.r. since it is a composition of p.r. functions. 
Or of course you could alternatively, more simply, define the function $\mathit{exp_2}(n) = 2^n$ by

$\mathit{exp_2}(0) = 1$,
$\mathit{exp_2}(Sn) = \mathit{mult}(\mathit{exp_2}(n), 2)$. 

and then put

$H(m) = \mathit{exp_2}(\mathit{mult}(m, m))$.

A: We note that all primitive recursive functions $p(x,y)$ defined by primitive recursion are of the form, $$p(x,y) =
\begin{cases}
p(x,0)= g(x) \\
p(x,Sy)= h(x,y,p(x,y)) \\
\end{cases}$$
Firstly, we define sum$(x,y)$ by primitive recursion as follows,
$$\text{sum}(x,y) =
\begin{cases}
\text{sum}(x,0) = I_{1}^{1}(x) \\
\text{sum}(x,Sy) = S(I_{3}^{3}(x,y,\text{sum}(x,y)))
\end{cases}$$
This defines that $x + 0 = x$ and that $x + Sy = S(x+y)$, which are both axioms of $PA$. Thus, sum$(x,y)$ is defined by primitive recursion and composition from initial functions $S$ and $I_{i}^{k}$, so we may conclude that sum$(x,y)$ is a primitive recursive function. Secondly, we define prod$(x,y)$ by primitive recursion as follows,
$$\text{prod}(x,y) =
\begin{cases}
\text{prod}(x,0) = \mathcal{Z}(x) \\
\text{prod}(x,Sy)= \text{sum}(I_{3}^{3}(x,y,\text{prod}(x,y)),I_{1}^{3}(x,y,\text{prod}(x,y)))
\end{cases}$$
This defines that $x \times 0 = 0$ and that $x \times Sy = (x \times y) + x$, as desired. Thus, prod$(x,y)$ is defined by primitive recursion and composition from the initial functions $S$, $I_{i}^{k}$, and $\mathcal{Z}$, so we may conclude that prod$(x,y)$ is a primitive recursive function. Thirdly, we define exp$(x,y)$ by primitive recursion as follows,
$$\text{exp}(x,y) = 
\begin{cases}
\text{exp}(x,0) = S(\mathcal{Z}(x)) \\
\text{exp}(x,Sy) = \text{prod}(I_{3}^{3}(x,y,\text{exp}(x,y)),I_{1}^{3}(x,y,\text{exp}(x,y))) \\
\end{cases}$$
This defines that $x^0 = 1$ and that $x^{Sy} = x^y \times x$. Thus, exp$(x,y)$ is defined by primitive recursion and composition from the initial functions $S$, $I_{i}^{k}$, and $\mathcal{Z}$, so we may conclude that exp$(x,y)$ is a primitive recursive function.
