Sum of roots^16

[terryds]

Homework Statement

Roots of the equation x³ - x + 1 = 0 are a, b, and c.
Determine the value of a¹⁶+b¹⁶+c¹⁶ !

Homework Equations

For ax³+bx²+cx+d = 0
x₁+x₂+x₃ = -b/a
x₁ * x₂ * x₃= -d/a

The Attempt at a Solution

[/B]
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...
Please help me how to solve this easily

 

[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!?

 

[terryds]

Try to determine a b and c and then you can find out teh value of any polynomial in a, b and c!

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

 

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

 

[terryds]

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.

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

 

[haruspex]

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

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.

 

[terryds]

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.

$(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?

 

[haruspex]

$(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?

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

 

[terryds]

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

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

I did it slightly differently than haruspex, it may or may not be more tedious.

You could notice that $a³ =a-1$.
⇒ $a^4 =a²-a$
⇒ $a^8= (a²-a)² = \cdots$
$a^8$ may contain terms in $a^4,a^3$,but you can replace them with the simpler expression in terms of $a²,a$.
And then compute $a^{16}$ by squaring $a^8$. After again simplifying you should get an expression for $a^{16}$ in terms of $a²,a$.
The same of course holds for $b^{16},c^{16}$, so adding the three, and using what you found with Vieta's formulas, should give the desired result.

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

 

[Samy_A]

Great!

Given this ...

Such a crazy problem in a two-hour test with 100 questions and no calculator...

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

 

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

 

[haruspex]

Great!

Given this ...

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

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 a₀=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 a₄=90.

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

 

[terryds]

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.

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!

 

[haruspex]

Newton's theorem is the most efficient way as far as I see. Thanks for your suggestion!

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.

 

[epenguin]

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