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.