Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

migrated from programmers.stackexchange.com Feb 9 '13 at 16:08

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

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.