How to Calculate the Sum of Coefficients in a Polynomial with known Integer Roots

Question

I have this problem: given $N$, $1 \leq N\leq 100$ integers which are roots from a polynomial, calculate the sum of coefficients from that polynomial

for example: given $3$ integers $2$, $2$ and $3$, I can calculate the polynomial $$x^3 - 7x^2 +16x -12,$$ so the sum of coefficients is $-2$

but if I have $100$ integers, I think calculating the polynomial will be enormous, so is there some way to find this sum of coefficients?

I'm sorry, what is monic? I'm a computer teacher, and this problem is a practice problem for computer science olympiad in Indonesia — Irawan Tan, Aug 06 '14 at 08:04
monic polynomial means a polynomial with leading coefficient (coefficient of the highest degree term) is $1$ — Bumblebee, Aug 06 '14 at 08:07
I think it's monic, because if all the roots are integer, so the coefficent of x^N must be 1 — Irawan Tan, Aug 06 '14 at 08:11

Jack D'Aurizio · Accepted Answer · 2019-08-25T17:54:34.193

8

The sum of the coefficients is just the value of the polynomial in $1$, hence if the polynomial is monic with roots in $n_1,\ldots,n_k$, then $$p(1) = (1-n_1)\cdot\ldots\cdot(1-n_k).$$

edited Aug 25 '19 at 17:54

answered Aug 06 '14 at 07:57

Jack D'Aurizio

353,855

I'm sorry, my background is in information technology, so can you explain the idea behind your answer. I have already created a Pascal submission using your equation above and it has been judged correct – Irawan Tan Aug 06 '14 at 08:08
In particular, if $1$ is a root, then the sum of the coefficients is zero. – Mark Bennet Aug 06 '14 at 08:30
1

And for the given example $(1-2)(1-2)(1-3)=-2$. – Aug 06 '14 at 08:46
@YvesDaoust, thanks for the explanation. – NoChance Aug 25 '19 at 08:49

score 1 · Answer 2 · answered Aug 06 '14 at 08:00

1

If your polynomial is monic, it can be written as $$P(x)=(x-1)(x-2)(x-3)...(x-100)= x^{100}+a_{99}x^{99}+...a_1x+a_0$$ put $x=1,$ then $$0=1+a_{99}+a_{98}+...a_1+a_0.$$

answered Aug 06 '14 at 08:00

Bumblebee

18,220
5
47
87

The roots are not necessarily $1,2,\dots,N$. – JiK Aug 06 '14 at 08:02
Thank you. But I think question says like that? – Bumblebee Aug 06 '14 at 08:09
The roots are random integer numbers not a sequential integer numbers. But your answer combined with the answer from Jack D'Aurizio helps me understand how to tackle this problem. Thx – Irawan Tan Aug 06 '14 at 08:16

How to Calculate the Sum of Coefficients in a Polynomial with known Integer Roots

2 Answers2

Linked

Related