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.
Best Answer
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.