AlgebraDifficulty 45-9535 tagged problems

Newton's Sums

Newton's Sums is the habit of turning sums of powers of the roots into the polynomial's coefficients. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$p_k - e_1 p_{k-1} + e_2 p_{k-2} - \cdots + (-1)^{k-1} e_{k-1} p_1 + (-1)^{k} k\, e_k = 0,$$ where $p_k = \sum_i r_i^{\,k}$ and $e_i$ are the elementary symmetric functions of the roots.

Newton's identities give a recurrence that computes the power sums of a polynomial's roots directly from its coefficients, so you never have to find the roots themselves.

Why It Works

1
For a monic polynomial with roots $r_i$, Vieta's formulas identify the elementary symmetric sums $e_i$ with (signed) coefficients.
2
Newton's identities tie the power sums $p_k = \sum_i r_i^{\,k}$ to those $e_i$ recursively; the first few read $p_1 = e_1$, $p_2 = e_1 p_1 - 2e_2$, and $p_3 = e_1 p_2 - e_2 p_1 + 3e_3$.
3
Each step only needs the already-computed lower power sums and the symmetric functions, so you build $p_1, p_2, p_3, \dots$ in order.
4
This converts a question about $\sum r_i^{\,k}$ (hard to get from roots) into pure coefficient arithmetic.

Worked Examples

Example 1

The roots of $x^3 - 6x^2 + 11x - 6 = 0$ are $r_1, r_2, r_3$. Find $r_1^2 + r_2^2 + r_3^2$ and $r_1^3 + r_2^3 + r_3^3$ without solving for the roots.

1
Read off the symmetric functions from the coefficients: $e_1 = 6$, $e_2 = 11$, $e_3 = 6$.
2
Power sum $p_1 = e_1 = 6$. Then $p_2 = e_1 p_1 - 2e_2 = 6\cdot 6 - 2\cdot 11 = 36 - 22 = 14$.
3
Next $p_3 = e_1 p_2 - e_2 p_1 + 3e_3 = 6\cdot 14 - 11\cdot 6 + 3\cdot 6 = 84 - 66 + 18 = 36$. (Check: the roots are $1, 2, 3$, and $1 + 4 + 9 = 14$, $1 + 8 + 27 = 36$.)

Answer:

$r_1^2 + r_2^2 + r_3^2 = 14$ and $r_1^3 + r_2^3 + r_3^3 = 36$.

Warm-up

The roots of $x^2 - 5x + 6 = 0$ are $r_1, r_2$. Find $r_1^2 + r_2^2$ using Newton's sums.

1
Read symmetric functions from the coefficients: $e_1 = 5$, $e_2 = 6$.
2
Power sum $p_1 = e_1 = 5$.
3
Then $p_2 = e_1 p_1 - 2e_2 = 5\cdot 5 - 2\cdot 6 = 25 - 12 = 13$. (Roots $2, 3$: $4 + 9 = 13$.)

Answer:

$r_1^2 + r_2^2 = 13$.

Contest level

Let $r_1, r_2, r_3$ be the roots of $x^3 - x - 1 = 0$. Find $r_1^3 + r_2^3 + r_3^3$.

1
There is no $x^2$ term, so $e_1 = 0$; the coefficients give $e_2 = -1$ and $e_3 = 1$.
2
Build the power sums: $p_1 = e_1 = 0$; $p_2 = e_1 p_1 - 2e_2 = 0 - 2(-1) = 2$.
3
Then $p_3 = e_1 p_2 - e_2 p_1 + 3e_3 = 0 - (-1)(0) + 3(1) = 3$.

Answer:

$r_1^3 + r_2^3 + r_3^3 = 3$.

Olympiad / Challenge

For the same roots of $x^3 - x - 1 = 0$, find $r_1^5 + r_2^5 + r_3^5$.

1
With $e_1 = 0$, $e_2 = -1$, $e_3 = 1$ and $p_1 = 0$, $p_2 = 2$, $p_3 = 3$, continue the recurrence (no $e_4, e_5$ terms for a cubic): $p_4 = e_1 p_3 - e_2 p_2 + e_3 p_1 = 0 - (-1)(2) + (1)(0) = 2$.
2
Then $p_5 = e_1 p_4 - e_2 p_3 + e_3 p_2 = 0 - (-1)(3) + (1)(2) = 3 + 2 = 5$.
3
Sanity check via the defining relation $r^3 = r + 1$: then $r^5 = r^2 r^3 = r^2(r + 1) = r^3 + r^2 = (r + 1) + r^2$, so $\sum r^5 = \sum 1 + p_1 + p_2 = 3 + 0 + 2 = 5$. ✓

Answer:

$r_1^5 + r_2^5 + r_3^5 = 5$.

Going Deeper

Generalization: for degree $n$ and $k > n$ the identity has no $e_k$ term and reads $p_k = e_1 p_{k-1} - e_2 p_{k-2} + \cdots + (-1)^{n-1} e_n p_{k-n}$ — a constant-coefficient linear recurrence, the same one a root satisfies via its own minimal polynomial.
Where it appears: AIME problems for $\sum r_i^k$ from a polynomial's coefficients, computing traces of matrix powers (power sums of eigenvalues), and proving symmetric-function identities.
Pitfall: mind the EXACT signs and the special leading term $(-1)^k k\,e_k$ — for $k \le n$ the formula carries an explicit factor of $k$ on $e_k$ (e.g. $p_2 = e_1 p_1 - 2e_2$, note the $2$; $p_3$ has $+3e_3$). Dropping that integer multiplier is the most common Newton's-sums mistake.

Spot the Signal

Use it when you need $\sum r_i^k$ but solving for the roots is impractical.
You can describe the hard part as turning sums of powers of the roots into the polynomial's coefficients, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by writing the Newton's-sum recurrence that links the power sums to the elementary symmetric functions.
Name the relation that makes Newton's Sums legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Mixing up the sign convention of the coefficients or the index in the recurrence.
Applying Newton's Sums because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let the coefficients carry the roots; never solve the polynomial you don't have to.

Try it on:

Compute a power sum of a polynomial's roots without solving for them.

Back to techniques

AlgebraDifficulty 45-9535 tagged problems

Newton's Sums

Practice this technique Match my level

The Key Result

$$p_k - e_1 p_{k-1} + e_2 p_{k-2} - \cdots + (-1)^{k-1} e_{k-1} p_1 + (-1)^{k} k\, e_k = 0,$$ where $p_k = \sum_i r_i^{\,k}$ and $e_i$ are the elementary symmetric functions of the roots.

Newton's identities give a recurrence that computes the power sums of a polynomial's roots directly from its coefficients, so you never have to find the roots themselves.

Why It Works

1
For a monic polynomial with roots $r_i$, Vieta's formulas identify the elementary symmetric sums $e_i$ with (signed) coefficients.
2
Newton's identities tie the power sums $p_k = \sum_i r_i^{\,k}$ to those $e_i$ recursively; the first few read $p_1 = e_1$, $p_2 = e_1 p_1 - 2e_2$, and $p_3 = e_1 p_2 - e_2 p_1 + 3e_3$.
3
Each step only needs the already-computed lower power sums and the symmetric functions, so you build $p_1, p_2, p_3, \dots$ in order.
4
This converts a question about $\sum r_i^{\,k}$ (hard to get from roots) into pure coefficient arithmetic.

Worked Examples

Example 1

The roots of $x^3 - 6x^2 + 11x - 6 = 0$ are $r_1, r_2, r_3$. Find $r_1^2 + r_2^2 + r_3^2$ and $r_1^3 + r_2^3 + r_3^3$ without solving for the roots.

1
Read off the symmetric functions from the coefficients: $e_1 = 6$, $e_2 = 11$, $e_3 = 6$.
2
Power sum $p_1 = e_1 = 6$. Then $p_2 = e_1 p_1 - 2e_2 = 6\cdot 6 - 2\cdot 11 = 36 - 22 = 14$.
3
Next $p_3 = e_1 p_2 - e_2 p_1 + 3e_3 = 6\cdot 14 - 11\cdot 6 + 3\cdot 6 = 84 - 66 + 18 = 36$. (Check: the roots are $1, 2, 3$, and $1 + 4 + 9 = 14$, $1 + 8 + 27 = 36$.)

Answer:

$r_1^2 + r_2^2 + r_3^2 = 14$ and $r_1^3 + r_2^3 + r_3^3 = 36$.

Warm-up

The roots of $x^2 - 5x + 6 = 0$ are $r_1, r_2$. Find $r_1^2 + r_2^2$ using Newton's sums.

1
Read symmetric functions from the coefficients: $e_1 = 5$, $e_2 = 6$.
2
Power sum $p_1 = e_1 = 5$.
3
Then $p_2 = e_1 p_1 - 2e_2 = 5\cdot 5 - 2\cdot 6 = 25 - 12 = 13$. (Roots $2, 3$: $4 + 9 = 13$.)

Answer:

$r_1^2 + r_2^2 = 13$.

Contest level

Let $r_1, r_2, r_3$ be the roots of $x^3 - x - 1 = 0$. Find $r_1^3 + r_2^3 + r_3^3$.

1
There is no $x^2$ term, so $e_1 = 0$; the coefficients give $e_2 = -1$ and $e_3 = 1$.
2
Build the power sums: $p_1 = e_1 = 0$; $p_2 = e_1 p_1 - 2e_2 = 0 - 2(-1) = 2$.
3
Then $p_3 = e_1 p_2 - e_2 p_1 + 3e_3 = 0 - (-1)(0) + 3(1) = 3$.

Answer:

$r_1^3 + r_2^3 + r_3^3 = 3$.

Olympiad / Challenge

For the same roots of $x^3 - x - 1 = 0$, find $r_1^5 + r_2^5 + r_3^5$.

1
With $e_1 = 0$, $e_2 = -1$, $e_3 = 1$ and $p_1 = 0$, $p_2 = 2$, $p_3 = 3$, continue the recurrence (no $e_4, e_5$ terms for a cubic): $p_4 = e_1 p_3 - e_2 p_2 + e_3 p_1 = 0 - (-1)(2) + (1)(0) = 2$.
2
Then $p_5 = e_1 p_4 - e_2 p_3 + e_3 p_2 = 0 - (-1)(3) + (1)(2) = 3 + 2 = 5$.
3
Sanity check via the defining relation $r^3 = r + 1$: then $r^5 = r^2 r^3 = r^2(r + 1) = r^3 + r^2 = (r + 1) + r^2$, so $\sum r^5 = \sum 1 + p_1 + p_2 = 3 + 0 + 2 = 5$. ✓

Answer:

$r_1^5 + r_2^5 + r_3^5 = 5$.

Going Deeper

Generalization: for degree $n$ and $k > n$ the identity has no $e_k$ term and reads $p_k = e_1 p_{k-1} - e_2 p_{k-2} + \cdots + (-1)^{n-1} e_n p_{k-n}$ — a constant-coefficient linear recurrence, the same one a root satisfies via its own minimal polynomial.
Where it appears: AIME problems for $\sum r_i^k$ from a polynomial's coefficients, computing traces of matrix powers (power sums of eigenvalues), and proving symmetric-function identities.
Pitfall: mind the EXACT signs and the special leading term $(-1)^k k\,e_k$ — for $k \le n$ the formula carries an explicit factor of $k$ on $e_k$ (e.g. $p_2 = e_1 p_1 - 2e_2$, note the $2$; $p_3$ has $+3e_3$). Dropping that integer multiplier is the most common Newton's-sums mistake.

Spot the Signal

Use it when you need $\sum r_i^k$ but solving for the roots is impractical.
You can describe the hard part as turning sums of powers of the roots into the polynomial's coefficients, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by writing the Newton's-sum recurrence that links the power sums to the elementary symmetric functions.
Name the relation that makes Newton's Sums legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Mixing up the sign convention of the coefficients or the index in the recurrence.
Applying Newton's Sums because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let the coefficients carry the roots; never solve the polynomial you don't have to.

Try it on:

Compute a power sum of a polynomial's roots without solving for them.