  We study the expressive power of polynomial recursive sequences, a nonlinear
extension of the well-known class of linear recursive sequences. These
sequences arise naturally in the study of nonlinear extensions of weighted
automata, where (non)expressiveness results translate to class separations. A
typical example of a polynomial recursive sequence is b_n=n!. Our main result
is that the sequence u_n=n^n is not polynomial recursive.
