Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was carefully reading section 1.2.9 subsection D: Change of z in a generating function. I don't understand the premises and Knuths reasoning in the marked paragraphs. First 2 paragraphs I can prove myself.

enter image description here

share|cite|improve this question

migrated from Feb 9 '13 at 16:08

This question came from our site for professional programmers interested in conceptual questions about software development.

up vote 1 down vote accepted

The part you can read is a special case of the part you're having trouble with. In the part you can read, omega (the script w looking thing) is a square root of 1, which is 1 or -1. (Both of them can be written as complex numbers as well, 1+0i and -1+0i.) In the two equations labeled (12), he's using these two roots (1 and -1) to extract the odd and even terms (m=2 in this case, so n mod m = r where r is 0 for even and 1 for odd).

There are 3 complex cube roots of unity: 1, -1/2 + (sqrt(3)/2)i, and -1/2 - (sqrt(3)/2)i. In his example, he uses a complex cube root to extract every third term starting at 1.

The wikipedia page on roots of unity might be helpful, especially the two pictures which show the 3rd and 5th roots of unity on a unit circle in the complex plane.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.