# how can prove $n^n$ is primitive recursive

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.

• If you know $f(x,y)=x^y$ is primitive recursive, can’t you just apply the composition axiom to get that $g(n)=f(n,n)$ is as well?
– Eric
Dec 8 '21 at 4:37
• I know, but I wanted to see if I could show it without using $x ^ y$ Dec 8 '21 at 5:06

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.
• "the number of multiplication functions is fixed as $(n-1)$" .... No. $n$ is a variable, so $n \times (n \times(...n \times (n \times n))...))$ is not a closed formula, and thus not a straightforward composition of multiplications. You really need primitive recursion to do this. Dec 8 '21 at 20:27
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.