Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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$.

share|improve this answer
    
Great answer! Could you show how you got there? –  Anonymous Mar 1 at 23:51
2  
I'd have to re-work it - believe it or not, I got it from memory. It's pretty clear that it must be of the form $\sum_{i+2j+3k=n} a_{i,j,k} x^iy^jz^k$, since it these $x^iy^jz^k$ are the ones of degree $n$. –  Thomas Andrews Mar 1 at 23:56
    
That is unbelievable. Kudos! Nonetheless, when you get a chance, I would appreciate if you could rework it and post a complete answer to everyone's benefit. –  Anonymous Mar 1 at 23:57
    
Why is the coefficient of $t^n$ what it is? I don't see it. –  Anonymous Mar 2 at 1:58
1  
It's just applying the trinomial theorem to $(xt+yt^2+zt^3)^k$ for each $k$ and then combining terms for each $N$. –  Thomas Andrews Mar 2 at 2:24

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.)

share|improve this answer

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}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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