# Welcoming 2016 with a Polynomial.

$x^{2016}-x^{2015}+x^{2014}-\cdots+x^{2} -x+1$/extract_itex] has roots , $x_{1},x_{2},\ldots,x_{2016}$. Evaluate $\left ( \displaystyle \sum_{k=1}^{2016}\sum_{i=1}^{2016}(1+x_{i})^{k} \right )$ Note by A Former Brilliant Member 4 years, 1 month ago This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science. When posting on Brilliant: • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused . • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone. • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge. • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events. MarkdownAppears as *italics* or _italics_ italics **bold** or __bold__ bold - bulleted- list • bulleted • list 1. numbered2. list 1. numbered 2. list Note: you must add a full line of space before and after lists for them to show up correctly paragraph 1paragraph 2 paragraph 1 paragraph 2 [example link](https://brilliant.org)example link > This is a quote This is a quote  # I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world" # I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world" MathAppears as Remember to wrap math in $$ ... $$ or \[ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

@Calvin Lin , what is your opinion for this ? What will be your approach ?

- 4 years, 1 month ago

Cool problem .... the new problem which is based on our yesterday's conversation ...

- 4 years, 1 month ago

Yes, thanks for that suggestion! For square-free numbers the count turns out to be pretty easy... the general case is a mess, though! Nobody has solved it yet... I'm counting on you!

- 4 years, 1 month ago

Bonus problem is complicated though @Otto Bretscher

- 4 years, 1 month ago

No it's not! Not for a guy like you ;)

- 4 years, 1 month ago

@Otto Bretscher , do we need to find a polynomial whose roots are , $2017 , 2017^2 ,.... 2017^2016$ ? As the inner summation is 2017 @Aareyan Manzoor help

- 4 years, 1 month ago

@Otto Bretscher , @Aareyan Manzoor , I have slight doubt ,

the inner summation will be definitely 2017.

So we need a polynomial whose roots are , $2017^{1} , 2017^{2} , 2017^{3} , .... , 2017^{2016}$ , isnt it ?

- 4 years, 1 month ago

nope.

- 4 years, 1 month ago

So am I right or wrong ? @Aareyan Manzoor

- 4 years, 1 month ago

@Aareyan Manzoor , but why ?

- 4 years, 1 month ago

i dont get "we seek a polynomial ...."

- 4 years, 1 month ago

sorry we need a polynomial , so that we can find the summation using vieta , @Aareyan Manzoor

- 4 years, 1 month ago

we really didnt use vietas. otto sir used roots of unity, i used a version of newtons sum.

- 4 years, 1 month ago

But can this be solved by vieta ? according to me it could not @Aareyan Manzoor

- 4 years, 1 month ago

i think not....

- 4 years, 1 month ago

Aareyan, are you not using Viete to make sure that the symmetric sums of the $x_i$ are zero?

- 4 years, 1 month ago

Lets try again write a solution on the work that you have done , on vieta approach , then I will post mine @Aareyan Manzoor , @Otto Bretscher

- 4 years, 1 month ago

In my approach, I'm not using Viete and I certainly don't need such a polynomial.

- 4 years, 1 month ago

I am just asking whether my approach is right ? (by vieta) @Otto Bretscher

- 4 years, 1 month ago

@Otto Bretscher , but please also see the vieta approach ,,, is it right ?

- 4 years, 1 month ago

Yes, Aareyan is applying Viete to the polynomial $x^{2017}+1$... that works.

- 4 years, 1 month ago

-1 is obviously not a root. we multiply by (x+1) to find $f(x)=x^{2017}+1=0$ one root of this expression is -1, and if we put it in the sum,i.e. $(1+x_i)=(1-1)=0$. so we can go on withput worries. we are just searching for: $\sum_{k=1}^{2016}\sum_{i=1}^{2017} (x_i+1)^k=\sum_{i=1}^{2017} (\dfrac{(x_i+1)^{2017}-1}{x_i+1-1}-1)=\sum_{i=1} (x_i^{2016}+\binom{2017}{1}x_i^{2015}+....+\binom{2017}{2016}-1)$ gp used here. view this.yes, the sum of all 2016th to 1st power is zero. the $\binom{2017}{2016}-1=2016$is left. added 2017 times results in $2016*2017=\boxed{4066272}$

- 4 years, 1 month ago

There may be a small error in the count (or rather two errors that cancel out). Your sum actually involves 2017 $i$'s (you have added -1) but you have to subtract 1 from the summand.

- 4 years, 1 month ago

i have said that "one root of this expression is -1...". at the first.

- 4 years, 1 month ago

So when you add up $\sum_{i}$ you have 2017 terms.

- 4 years, 1 month ago

i have said why we can neglect -1, reducing a root and giving us 2016 terms.

- 4 years, 1 month ago

But if you use only 2016 terms then it is no longer true that the sum of the 2016th to first powers is zero. Think about it... you will see what I mean.

- 4 years, 1 month ago

true... the answer should be $2017^2$?

- 4 years, 1 month ago

No, there is another small error that compensates for this one... you are losing a term $-1$ along the way... the constant term in your sum should be 2017-1=2016, so it all works out... a Christmas miracle ;)

- 4 years, 1 month ago

sorry for late response( electricity...), what a miracle indeed, i have edited it.

- 4 years, 1 month ago

One more small correction: In your double sum, it is $i$ that goes to 2017, not $k$.

- 4 years, 1 month ago

corrected once again...

- 4 years, 1 month ago

Taking a quick look at this during our x-mas festivities, I would suspect that the inner sum is always 2017, so that the whole sum would be 2016*2017.

[added later] We observe that the $y_i=-x_i$, together with $y_0=1$, are the 2017th roots of unity. Now

$\sum_{k=1}^{2016}\sum_{i=0}^{2016}(1-y_i)^k=\sum_{k=1}^{2016}\sum_{i=0}^{2016}(1-ky_i+....\pm y_i^{k})=\sum_{k=1}^{2016}2017=2016*2017$

since the sum of the $j$th powers of the 2017th roots of unity is 0 for $j\leq 2016$.

- 4 years, 1 month ago

@Otto Bretscher , please try to solve using Vieta.

- 4 years, 1 month ago

My solution is quite short and straightforward.... why should I look for another solution? ;) (I guess I could use Viète to prove that the sum of the $j$th powers of the roots of unity is 0)

- 4 years, 1 month ago

yes,you are right @Otto Bretscher, please view my comment when you have time.

- 4 years, 1 month ago

I thought about it in a slightly different but equivalent way.

We observe that the $y_i=-x_i$, together with $y_0=1$, are the 2017th roots of unity. Now $\sum_{i=0}^{2016}(1-y_i)^k$$=\sum_{i=0}^{2016}(1-ky_i+....\pm y_i^{k})=2017$ since the sum of the $j$th powers of the 2017th roots of unity is 0.

- 4 years, 1 month ago

hmm... i wrote that feature in my wiki "roots of unity" and proved it by the linked note. the same thing really.

- 4 years, 1 month ago

This also would work

- 4 years, 1 month ago