Algebraic algorithm using Viete's formula Does anyone know of an algorithm for computing $a^n + b^n + c^n$ given $$x = a + b + c, y = ab + bc + ac, z = abc?$$
Or at least, for small integers $n$?
Lastly, is there any software that can do something like this?
 A: You can write it as:
$$a^n+b^n+c^n=\sum_{i+2j+3k=n} (-1)^j\frac{n}{i+j+k}\binom{i+j+k}{i,j,k} x^iy^jz^k$$
The fundamental reasoning is to write the power series:
$$\begin{align}\sum_{n=0}^\infty (a^n+b^n+c^n)t^n &= \frac{1}{1-at}+\frac{1}{1-bt}+\frac{1}{1-ct}\\&=\frac{3-2xt+yt^2}{1-xt+yt^2-zt^3}\end{align}$$
Then expand: $$\frac{1}{1-xt+yt^2-zt^3} = \sum_{k=0}^\infty (xt-yt^2+zt^3)^k$$
What is the coefficient of $t^N$ in this power series? It is $$\sum_{i+2j+3k=N} (-1)^j \binom{i+j+k}{i,j,k}x^iy^jz^k$$
But the rest gets messy, because you have to multiply that by $3-2xt+yt^2$. 
A: This can be done recursively using Newton's identities, which state
$$ke_k=\sum_{i=1}^{k-1}(-1)^{i-1}e_{k-i}p_i$$
where $p_k$ and $e_k$ are the power and elementary symmetric polynomials (resp) given by
$$p_k=a_1^k+\cdots+a_m^k \qquad e_k=\sum_{1\le i_1<\cdots<i_k\le m}a_{i_1}\cdots a_{i_k}$$
The number of variables $m$ is irrelevant. See the Wikipedia article for more information.
(One can express the $e_k$ polynomials explicitly in terms of $p_i$s via a trace formula for Schur functors in representation theory. I am not aware if there is a reversal of this.)
A: Applying the simple method here to the power sum $\,f_n = a^n+b^n+c^n\,$ we obtain a recurrence in terms of tbe $\,n$-shift operator $\,S g(n) = g(n+1)$
$$\begin{eqnarray} 0 &=& (S-a)(S-b)(S-c)\,f_n\\ \\
&\ =\ & (S^3-\,(a\!+\!b\!+\!c)\ S^2\,+\ (ab\!+\!bc\!+\!ca)\ \, S\ -\ abc)\,f_n\\ \\
&=& f_{n+3}\!-(a\!+\!b\!+\!c)f_{n+2}\!+(ab\!+\!bc\!+\!ca)f_{n+1}\! -abc\, f_n \\ \\
&=& f_{n+3} - x\, f_{n+2} + y\, f_{n+1} - z\, f_n
\end{eqnarray}$$ 
