What is the sum of the nth roots of unity? What is their product if n is odd? If n is even?

Short Answer

Expert verified

Sum of nth root of unity =0

Product of nth root of unity, when number of terms are even =-1

Product of nth root of unity, when number of terms are odd =1

Step by step solution

01

Sum of  n th root of unity

Thenthrootsofunityare1,W,W2,W3,....WN-1Where,W=e2πn=cos2πnθ+isin2πnθ

The sum of nth roots of unity is:

1,W,W2,W3,.....WN-1 …… (1)

As per the geometric series, the sum of n terms of 1,W,W2,W3,.....WN-1is represented as .

So, equation (1) can be represented as follows:

Sum of nth root of unity= 1-wn1-w

=1-cos2πn+isin2πn1-cos2πn+isin2πn=1-cos2π+isin2π1-cos2πn+isin2πn=1-1+01-cos2πn+isin2πn=1-11-cos2πn+isin2πn=0

02

Product of nth root of unity 

The production of th root unity are following: 1,W,W2,W3,....WN-1...3... (3)

As per the arithmetic series, the product of n terms of 1,W,W2,W3,....WN-1is

represented as role="math" localid="1658921404734" Wnn-12

So, calculation (3) is present as follows:

Product of th root of unity =Wnn-12

=cos2n+isin2nnn-12 ... (4)

If is even, then

Product of nth root of unity =-1 … (5)

If n is odd, then

Product of nth root of unity =1 … (6)

Moreover,

  • This summation of such nth component of unity is given by Equation (2), is equal to 0.
  • If "n" is even, this products of both the nth root for unity is obtained from Equation (5), is equal to -1.
  • If "n" is odd, the composite of nth roots of unity may be calculated using Equation (6), is equal to 1.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Suppose we want to evaluate the polynomial P(x) = a0 + a1x + a2x2 + ... + anxn at point x.

  1. Show that the following simple routine, known as Horner’s rule, does the job and leaves the answer in z.
    z = an
    for I = n-1 down to 0 :
    z = zx + ai
  2. How many additions and multiplications does this routine use, as a function of n ? Can you find a polynomial for which an alternative method is substantially better?

In justifying our matrix multiplication algorithm (Section 2.5), we claimed the following block wise property: if X and Y are n×nn matrices, and

X=[ABCD],Y=[EFGH],

where A,B,C,D,E,F,G, and H are n/2×n/2 sub-matrices, then the product XY can be expressed in terms of these blocks:

XY=[ABCD][EFGH]=[AE+BGAF+BHCE+DGCF+DH]

Prove this property.

Section 2.2 describes a method for solving recurrence relations which is based on analyzing the recursion tree and deriving a formula for the work done at each level. Another (closely related) method is to expand out the recurrence a few times, until a pattern emerges. For instance, let’s start with the familiar T(n)=2T(n/2)+o(n). Think of o(n) as being role="math" localid="1658920245976" <cnfor some constant , so: T(n)<2T(n/2)+cn. By repeatedly applying this rule, we can bound T(n) in terms of T(n/2), then T(n/4), then T(n/8), and so on, at each step getting closer to the value of T(.) we do know, namely .

T(1)=0(1).

T(n)2T(n/2)+cn2[2Tn/4+cn/2]+cn=4T(n/4)+2cn4[2Tn/8+cn/4]+2cn=8T(n/8)+3cn8[2Tn/16+cn/8]+3cn=16T(n/16)+4cn

.

.

.

A pattern is emerging... the general term is

T(n)2kT(n/2k)+kcn

Plugging in k=log2n, we get T(n)nT(1)+cnlog2n=0(nlogn).

(a)Do the same thing for the recurrence T(n)=3T(n/2)+0(n). What is the general kth term in this case? And what value of should be plugged in to get the answer?(b) Now try the recurrence T(n)=T(n-1)+0(1), a case which is not covered by the master theorem. Can you solve this too?

Practice with the fast Fourier transform.

(a) What is the FFT of (1,0,0,0)? What is the appropriate value of ωin this case? And of which sequence is (1,0,0,0)the FFT?

(b)Repeat for (1,0,1,-1).

Question: You are given an infinite array A[·]in which the first n cells contain integers in sorted order and the rest of the cells are filled with . You are not given the value of n. Describe an algorithm that takes an integer x as input and finds a position in the array containing x, if such a position exists, in O(log n) time. (If you are disturbed by the fact that the array A has infinite length, assume instead that it is of length n, but that you don’t know this length, and that the implementation of the array data type in your programming language returns the error message whenever elements A[i]withi>n are accessed.)

See all solutions

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free