Summing roots of unity

Algebra Level 5

Let the roots of x j = 1 x^j=1 be 1 , ω j 1 , ω j 2 , … ω j j − 1 \large 1, \omega_{j_{1}} , \omega_{j_{2}} , \dots \omega_{j_{j-1}} , then find the value of:

∑ j = 2 61 ∑ i = 1 j − 1 1 1 − ω j i \large \displaystyle \sum_{j=2}^{61} \sum_{i=1}^{j-1} \frac{1}{1 - \omega_{j_{i}}}


The answer is 915.

Jatin Yadav by jatin yadav , 23, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Jon Haussmann
Mar 7, 2014

We want to find S j = ∑ i = 1 j − 1 1 1 − ω j i . S_j = \sum_{i = 1}^{j - 1} \frac{1}{1 - \omega_{j_i}}. Let ω \omega be a primitive j j th root of unity. Then S j = ∑ i = 1 j − 1 1 1 − ω i . S_j = \sum_{i = 1}^{j - 1} \frac{1}{1 - \omega^i}.

Note that 1 1 − ω k + 1 1 − ω j − k = ( 1 − ω j − k ) + ( 1 − ω k ) ( 1 − ω k ) ( 1 − ω j − k ) = 2 − ω k − ω j − k 1 − ω k − ω j − k + 1 = 1. \begin{aligned} \frac{1}{1 - \omega^k} + \frac{1}{1 - \omega^{j - k}} &= \frac{(1 - \omega^{j - k}) + (1 - \omega^k)}{(1 - \omega^k)(1 - \omega^{j - k})} \\ &= \frac{2 - \omega^k - \omega^{j - k}}{1 - \omega^k - \omega^{j - k} + 1} \\ &= 1. \end{aligned}

Then 2 S j = ∑ k = 1 j − 1 ( 1 1 − ω k + 1 1 − ω j − k ) = ∑ k = 1 j − 1 1 = j − 1 , 2S_j = \sum_{k = 1}^{j - 1} \left( \frac{1}{1 - \omega^k} + \frac{1}{1 - \omega^{j - k}} \right) = \sum_{k = 1}^{j - 1} 1 = j - 1, so S j = ( j − 1 ) / 2 S_j = (j - 1)/2 .

Finally, ∑ j = 2 61 S j = ∑ j = 2 61 j − 1 2 = 915. \sum_{j = 2}^{61} S_j = \sum_{j = 2}^{61} \frac{j - 1}{2} = 915.

20 Helpful 0 Interesting 0 Brilliant 0 Confused

There are just certain sums that can be computed by writing out the terms backwards. This happens to be one of them.

Jon Haussmann - 7 years, 3 months ago

Nice pairing of the roots. What made you think of that?

Calvin Lin Staff - 7 years, 3 months ago

Good thinking.

Rajen Kapur - 7 years, 3 months ago

Nice idea

Hun-Min Park - 7 years, 2 months ago
Jatin Yadav
Mar 2, 2014

This problem is actually a mix of calculus and algebra.

Clearly, x j − 1 = ( x − 1 ) ∏ i = 1 j − 1 ( x − ω j i ) x^j-1 = (x-1) \displaystyle \prod_{i=1}^{j-1} (x - \omega_{j_{i}})

Hence, x j − 1 x − 1 = 1 + x + … x j − 1 = ∏ i = 1 j − 1 ( x − ω j i ) \frac{x^j-1}{x-1} = 1+x+ \dots x^{j-1} = \displaystyle \prod_{i=1}^{j-1} (x-\omega_{j_{i}})

Take log on both sides to get:

ln ⁡ ( 1 + x + … x j − 1 ) = ∑ i = 1 j − 1 ln ⁡ ( x − ω j i ) \ln(1+x+ \dots x^{j-1}) = \displaystyle \sum_{i=1}^{j-1} \ln(x-\omega_{j_{i}})

Now, differentiate both sides to get:

1 + 2 x + 3 x 2 + … ( j − 1 ) x j − 2 1 + x + … x j − 1 = ∑ i = 1 j − 1 1 x − ω j i \large \frac{1+2x+3x^2+\dots (j-1)x^{j-2}}{1+x+ \dots x^{j-1}} = \displaystyle \sum_{i=1}^{j-1} \frac{1}{x - \omega_{j_{i}}}

Replace x = 1 x=1 to get :

∑ i = 1 j − 1 1 1 − ω j i = ∑ r = 1 j − 1 r j = j − 1 2 \displaystyle \sum_{i=1}^{j-1} \frac{1}{1- \omega_{j_{i}}} = \frac{\sum_{r=1}^{j-1} r}{j} = \frac{j-1}{2}

Now again, we have to sum,

∑ j = 2 n ∑ i = 1 j − 1 1 1 − ω j i \displaystyle \sum_{j=2}^{n} \sum_{i=1}^{j-1} \frac{1}{1-\omega_{j_{i}}}

= ∑ j = 2 n j − 1 2 = n ( n − 1 ) 4 \displaystyle \sum_{j=2}^{n} \frac{j-1}{2} = \frac{n(n-1)}{4}

Replace n = 61 n=61 to get the answer as 915 \boxed{915}

16 Helpful 0 Interesting 0 Brilliant 0 Confused

There isn't a need to use calculus, since you are simply interested in a transformation of roots.

We have x j i x_{j_i} are the roots of the equation 1 + x + x 2 + … + x j − 1 = 0 1 + x + x^2 + \ldots + x^{j-1} = 0 . Consider the transformation y = 1 1 − x y = \frac{1}{1-x} , since we are interested in ∑ 1 1 − x i = ∑ y i \sum \frac{1}{1-x_i} = \sum y_i .

The transformation gives us 1 + y − 1 y + ( y − 1 ) 2 y 2 + … = 0 1 + \frac{y-1}{y} + \frac{(y-1)^2}{y^2} + \ldots = 0 . Multiplying throughout by y j − 1 y^{j-1} (which is non-zero) and collecting terms for y j − 1 , y j − 2 y^{j-1}, y^{j-2} , we find that the polynomial starts out as

j y j − 1 − j ( j − 1 ) 2 y j − 2 + … = 0 j y^{j-1} - \frac{ j(j-1) } { 2} y^{j-2} + \ldots = 0

Hence, we get that the sum of roots is ∑ y = j ( j − 1 ) 2 j = j − 1 2 \sum y = \frac{ \frac{ j(j-1) } { 2}} { j} = \frac{ j-1}{2} as claimed.

Calvin Lin Staff - 7 years, 3 months ago

Log in to reply

Yes you are true, nice solution.

jatin yadav - 7 years, 3 months ago

Did the same way as calvin sir did :) upvoted

Prakhar Bindal - 5 years, 4 months ago

Bravo! Well done!

Jit Ganguly - 7 years, 3 months ago

Nicely done, similar to what i did!!

Aabhas Mathur - 7 years, 2 months ago

Same approach

Aakash Khandelwal - 5 years, 8 months ago
Tong Zou
Mar 11, 2014

Let ω \omega be primitive j j th root of unity. Then the inner sum is

S j = ∑ i = 1 j − 1 1 1 − ω i \displaystyle S_{ j }=\sum _{ i=1 }^{ j-1 }{ \frac { 1 }{ 1-\omega ^i } } .

Take the conjugate on both sides, we get

S j ˉ = ∑ i = 1 j − 1 1 1 − ω ˉ i = ∑ i = 1 j − 1 1 1 − 1 ω i = ∑ i = 1 j − 1 − ω i 1 − ω i \displaystyle \bar{S_{ j }}=\sum _{ i=1 }^{ j-1 }{ \frac { 1 }{ 1-\bar { \omega } ^{ i } } } = \sum _{ i=1 }^{ j-1 }{ \frac { 1 }{ 1-\frac{1}{ \omega ^{ i }}} } = \sum _{ i=1 }^{ j-1 }{ \frac { -\omega^i }{ 1-\omega ^i } } .

Now it's easy to see that S j + S j ˉ = j − 1 \displaystyle S_{j}+\bar{S_{j}}=j-1 .

But S j ˉ \bar{S_j} is the same as S j S_j since ω ˉ \bar{\omega} is also a primitive j j th root of unity. Therefore S j = j − 1 2 S_j=\frac{j-1}{2} . The rest is easy.

4 Helpful 0 Interesting 0 Brilliant 0 Confused
Rushikesh Joshi
Apr 30, 2015

In equation x^j-1=0, replace x by (x-1)/x Sum of roots of new equation =jC2/jC1 =(j-1)/2 , now we want summation( j-1)/2 From j=2 to j=61 we get :1/2(61×62/2-1-60) ie 915

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...