# Sum of roots^16

Tags:
1. Apr 13, 2016

### terryds

1. The problem statement, all variables and given/known data

Roots of the equation x3 - x + 1 = 0 are a, b, and c.
Determine the value of a16+b16+c16 !

2. Relevant equations

For ax3+bx2+cx+d = 0
x1+x2+x3 = -b/a
x1 * x2 * x3= -d/a

3. The attempt at a solution

I know how to determine the value of a + b+ c but not a^16+b^16+c^16...
I think I can factor a^16+b^16+c^16 using binomial (Pascal's triangle) but I think it will take too much time
Such a crazy problem in a two-hour test with 100 questions and no calculator...

2. Apr 13, 2016

### Let'sthink

Try to determine a b and c and then you can find out the value of any polynomial in a, b and c! You know a+b+c, ab+bc+ca and abc!?

Last edited: Apr 14, 2016
3. Apr 14, 2016

### terryds

How to?
I figured out 1 and -1 are not the roots.
How to find out the roots of the equation?

4. Apr 14, 2016

### haruspex

There is a third equation relating the three roots of a cubic to its coefficients.
The trick is to massage these three equations into the form you need.

Take it in stages. Start with just squaring the equation for b/a.

5. Apr 14, 2016

### terryds

I still don't get it. I don't understand what you meant

Last edited: Apr 14, 2016
6. Apr 14, 2016

### haruspex

You quoted two standard equations, one involving b/a and one involving d/a. There is a third one, involving c/a. Look up Vieta.
If you take the one involving b/a and square both sides, on the left you will have a sum of squares of the roots and some other terms. The other terms can be replaced using the equation you are missing. The result is that you can effectively extend Vieta's equations to obtain one for the sum of the squares of the roots.
Continuing in the same way, you can get expressions for sums of higher powers of the roots.

7. Apr 14, 2016

### terryds

$(a+b+c)^2 = -\frac{B}{A} \\ a^2 + b^2 + c^2 - 2 (ab+ac+bc) =\frac{B^2}{A^2} \\ a^2 + b^2 + c^2 - 2 (\frac{C}{A}) = \frac{B^2}{A^2}\\ a^2 + b^2 + c^2 = \frac{B^2}{A^2} + 2 (\frac{C}{A})\\$

But, it's just power of 2.
So, should I square it again and again till the power reaches 16 ?
Is it the only way to do it?

8. Apr 14, 2016

### haruspex

I don't know a better way.
You have a sign error in the second line above.

9. Apr 14, 2016

### terryds

$a^2+b^2+c^2 = \frac{B^2}{A^2} - 2 \frac{C}{A}$

$a^8 = (a^2-a)^2 = a^4 - 2a^3 + a^2 = (a^2-a) - 2 (a-1) + a^2 = 2a^2 - 3a + 2 \\ a^{16} = (a^8)^2 = (2a^2 - 3a + 2)^2 = 4a^4 - 12 a^3 + 17 a^2 - 12a + 4 \\ = 4(a^2-a) - 12(a-1) + 17a^2 - 12a + 4 = 4a^2 -16a + 12 + 17a^2 - 12a + 4 \\ = 21a^2 - 28a + 16 \\ b^{16} = 21b^2 - 28b + 16 \\ c^{16} = 21c^2 - 28c + 16 \\ a^{16} + b^{16} + c^{16} = 21(a^2+b^2+c^2) - 28 (a+b+c) + 48 \\ a^{16} + b^{16} + c^{16} = 21((a+b+c)^2 - 2 (ab+ac+cb)) - 28 (a+b+c) + 48 \\ a^{16} + b^{16} + c^{16} = 21(0^2 - 2 (-1)) - 28 (0) + 48 = 21 (2) - 0 + 48 = 42+48 = 90$

Thank you for your help @haruspex , @Samy_A ,@Let'sthink !

10. Apr 14, 2016

### Samy_A

Great!

Given this ...
... I wonder if there is some smart easy method.

11. Apr 14, 2016

### epenguin

1 Doubt a question like this comes out of the blue. What have you been studying recently relevant?

2 In your 'relevant equations' you have given two out of three.

3 Look up Newton's theorem about sums of powers of roots.

12. Apr 14, 2016

### haruspex

It can be accelerated with a convenient notation.
Define $a_n=\Sigma_i \alpha_i^{2^n}$ and $b_n=\Sigma_{i< j} (\alpha_i\alpha_j)^{2^n}$.
Since the product of the roots is -1, it is not hard to show that $a_n^2=a_{n+1}+2b_n$ and for n>0 $b_n^2=b_{n+1}+2a_n$. At n=0, the second equation is the same except for a sign change, but since a0=0 that makes no difference.
Having established those two equations, it is a rapid process to fill in a table even up to powers of 32. And yes, it gives a4=90.

It would be interesting to find the general solution of that pair of recurrence relations. I note that a5=8090, which does not have very many factors.

13. Apr 14, 2016

### terryds

It's a tryout test for university entrance exam.
Newton's theorem is the most efficient way as far as I see. Thanks for your suggestion!

14. Apr 14, 2016

### haruspex

Doesn't look as efficient to me. The reference I found, https://artofproblemsolving.com/wiki/index.php?title=Newton's_Sums, shows stepping through all the exponents up to 16, instead of only having to deal with the powers of 2 exponents.

15. Apr 15, 2016

### epenguin

I think your paras 1 and 2 of #1 are garbled, mixing up definitions or notations of roots and coefficients.

Last edited: Apr 15, 2016