We say that a sequence $a(n)$ is $P$-recursive if there exist polynomials $p_0(n),\ldots,p_k(n) \in \mathbb{Q}[n]$ such that $$p_k(n) a(n+k) + \cdots p_0(n) a(n) = 0.$$
I would like to show that the sequence $a(n) = n^n$ is not $P$-recursive. The problem in question hints at the fact that $e$ is a transcendental number yet I do not see how to use this fact here.
Hence I would like to ask
How can one show that $n^n$ is not a $P$-recursive function?
Okay, suppose that $a(n)=n^n$ were $P$-recursive. We have $$p_k(n)(n+k)^{n+k}+\cdots+p_1(n)(n+1)^{n+1}+p_0(n)n^n=0$$ Let's divide through by $n^n$, and set $q_i(n)=p_i(n)(n+i)^i$. We now have $$q_k(n)(1+k/n)^n+\cdots +q_1(n)(1+1/n)^n+q_0(n)(1+0/n)^n=0$$ Now, set $t=\max\{\deg q_k(n), \ldots, \deg q_1(n), \deg q_0(n)\}$, and divide through by $n^t$, and take limits. If we set $a_i=\lim\limits_{n\to\infty} q_i(n)n^{-t}$, we have $a_i\in\mathbb{R}$ because $\deg q_i(n)\le t$. The result is $$a_ke^k+\cdots+a_1e^1+a_0e^0=0$$ At least one $a_i$ must be nonzero, which will give us a contradiction. If $i\ge 1$, then we have proved that $e$ is algebraic, which is a contradiction. If instead only $a_0\neq 0$, then we have the contradiction $a_0=0$.