1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$
    – Eric
    Dec 8 '21 at 4:37
  • $\begingroup$ I know, but I wanted to see if I could show it without using $ x ^ y $ $\endgroup$ Dec 8 '21 at 5:06
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ "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. $\endgroup$
    – Bram28
    Dec 8 '21 at 20:27
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.