how can prove $n^n$ is primitive recursive

Question

I try to prove $n^n$ is primitive recursive,first i try to releationate this proof with the proof of $x^y$, but in this case is different, because the base is not the same.

So my attempt was to see the relationship between $n^n$ and $(n + 1)^{(n+1)}$ by the newtons formula,an i got:
$ (n+1)^{(n+1)}= \sum_{k=0}^{\infty}\left(\begin{array}{l} n+1 \\ k \end{array}\right) n^{n+1-k} =\sum_{k=2}^{\infty}\left(\begin{array}{c} n+1 \\ k \end{array}\right) n^{n+1 - k}+\left(\begin{array}{l} n+1 \\ 0 \end{array}\right) n(n)^{n}+ \left(\begin{array}{l} n+1 \\ 1 \end{array}\right)n^n $
So i would think that I can express as a sum of $n ^ n$, but I'm not sure if this is the best way to do it.

Answer 1

First we know multiplication funtion is primitive recursive (multiplication is a doubly nested primitive recursions of the initial $S$-function), and also we know $f(n)=n^n=n \times (n \times(...n \times (n \times n))...))$ and the number of multiplication functions is fixed as $(n-1)$, so apparently $f(n)$ is a primitive recursion of multiplications. Since primitive recursion of p.r. functions is still p.r., so $f(n)=n^n$ is still primitive recursive. Note here for your example function we don't need any exponential function concept.

Answer 2

There is really no simpler way to do this than effectively doing the proof for primitive recursion of $x^y$ ... but with $x$ and $y$ being the same. Or, do what Eric says in the Comments: now that you know that $f(x,y)=x^y$ is primitive recursive, simply note that $g(n)=f(n,n)$ is therefore primitive recursive as well.