Newton's formula allows one to calculate the sum $S_n(P)$ of the $n$th powers of the roots of a given monic polynomial $P$ without finding the roots explicitly. (This works even when the roots themselves don't have a closed form.) If the polynomial is in $\mathbb{Z}[x]$, then the sum is an integer; further, the sequence $(S_n)^\infty_{n=1}$ is a homogeneous linear recurrence of order $\deg(P).$
I'm interested in turning this around: given a homogeneous linear recurrence and an integer sequence $(x_n)^\infty_{n=1}$ satisfying this recurrence, how can I tell if there is a monic integer polynomial $P$ such that $x_n$ is the sum of the $n$th powers of the roots of $P$? (If so, finding such a polynomial is also of interest.)
If the polynomial in the denominator of the generating functions has only simple roots (i.e. roots with multiplicity 1), a full partial fraction decomposition of the generating function with only have terms $\sim 1/(x-r)$ with roots $r$, and replacing these terms by their geometric series shows that the original series has the required shape (keyword: Binet formula). For roots of higher order, the partial fraction decomposition has also other terms.