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

Suppose $\omega$ is a primitive seventh root of unity. I would like to find as simple an expression as possible for $$ \sum_{j=0}^6 (1 + \omega^j)^n. $$

The book I am looking at gives $$ 2^n \left\lfloor 1+2\sum_{j=1}^3 \cos{\frac{\pi j n}{7}} \cos^n \frac{ \pi j}{j} \right\rfloor $$ with no explanation, and I am wondering how they got this. (I am also wondering if it is a typo, since this book seems to have quite a few --- if it is correct as written, why not cancel the rightmost $j$'s and rewrite $\cos^n \pi$ as $(-1)^n$?)


Motivation: this is the last step in simplifying the expression $$\sum_{k=0}^{\lfloor n / 7 \rfloor} {n \choose 7k}.$$ This is problem #42(f) in section 1 of Lovasz's Combinatorial Problems and Exercises, Second Edition. In my copy, the problem is on p. 21, and the solution (which makes sense until the last step) is on p. 195.

(To be clear, I have pulled out a factor of $\frac{1}{7}$ which appears somewhere along the way but is irrelevant to the above.)

share|cite|improve this question
For $n=1$ and $\omega=e^{i\pi/7}$, the top is +7 whereas the bottom is -6, there's got to be a typo. (Also, sometimes books don't cancel things right away to be more suggestive i.e. help the reader figure out how an expression was obtained.) – anon Oct 12 '11 at 21:48
Also, just for fun (when $\omega$ is primitive): $$\sum_{j=0}^6(1+\omega^j)^n=\sum_{j=0}^6\sum_{k=0}^n{n\choose k}\omega^{kj} =\sum_{k=0}^n{n\choose k}\sum_{j=0}^6\omega^{kj}=\sum_{0\le7k\le n}{n\choose 7k}$$ – anon Oct 12 '11 at 21:51
anon, (1) $\omega = e^{2 \pi i / 7}$ would be a primitive seventh root of unity rather than $e^{\pi i /7}$, and (2) very nice, in fact $$\sum_{k=0}^{\lfloor \frac{n}{7} \rfloor} {n \choose 7k}$$ is exactly the expression we are trying to simplify! This is supposed to be the last step. – Matthew Kahle Oct 12 '11 at 22:02
@anon: that is a much nicer formula, although more terms. However, I believe that it needs an extra factor of 7 in the rightmost term. – robjohn Oct 12 '11 at 22:07
Nevertheless, there seems to be an error in there somewhere. For $n=14$ the cosines are all $1$, so the bottom is just $7\cdot2^n$, whereas there's cancellation in the top so the upper bound $7\cdot2^n$ can't be attained. – joriki Oct 12 '11 at 22:09
up vote 4 down vote accepted

I think this is rather less mysterious than it looks and just resulted from a combination of two misprints. The floor function should be a bracket, and the $j$ in the denominator should be a $7$. Then the derivation is straightforward:

$$ \begin{align} \sum_{j=0}^6 \left(1 + \omega^j\right)^n &= \sum_{j=0}^6 \left(1 + \mathrm e^{2\pi\mathrm ij/7}\right)^n \\ &= \sum_{j=0}^6 \left(\mathrm e^{\pi\mathrm ij/7}\left(\mathrm e^{\pi\mathrm ij/7}+\mathrm e^{-\pi\mathrm ij/7}\right)\right)^n \\ &= \sum_{j=0}^6 \mathrm e^{\pi\mathrm ijn/7}\left(2\cos\frac{\pi j}7\right)^n \\ &= 2^n\sum_{j=0}^6 \mathrm e^{\pi\mathrm ijn/7}\cos^n\frac{\pi j}7 \\ &= 2^n\left(1+2\sum_{j=1}^3 \cos\frac{\pi jn}7\cos^n\frac{\pi j}7\right)\;. \end{align} $$

share|cite|improve this answer
I didn't mention the misprints, but I got the same answer. (+1) – robjohn Oct 12 '11 at 23:02
@robjohn: Well, you didn't mention the misprints, but you mentioned the signs, which I deftly ignored :-) – joriki Oct 12 '11 at 23:05

Using $1+e^{2\pi i/7\;j}=2\cos\left(\pi/7\;j\right)e^{\pi i/7\;j}$, we get $$ \sum_{j=0}^6(1+\omega^j)^n=2^n\sum_{j=0}^6\cos^n\left(\frac{\pi j}{7}\right)e^{\pi i/7\;nj}\tag{1} $$ Noting that each term in the sum can be paired with its conjugate, we see that the sum is real. Therefore, we can simply take the real part of $(1)$, which yields $$ \sum_{j=0}^6(1+\omega^j)^n=2^n\sum_{j=0}^6\cos^n\left(\frac{\pi j}{7}\right)\cos\left(\frac{\pi nj}{7}\right)\tag{2} $$ Using that $\cos^n\left(\frac{\pi(7-j)}{7}\right)=(-1)^n\cos^n\left(\frac{\pi j}{7}\right)$ and $\cos\left(\frac{\pi n(7-j)}{7}\right)=(-1)^n\cos\left(\frac{\pi nj}{7}\right)$ and $\cos(0)=1$, $(2)$ becomes $$ \sum_{j=0}^6(1+\omega^j)^n=2^n\left[1+2\sum_{j=1}^3\cos^n\left(\frac{\pi j}{7}\right)\cos\left(\frac{\pi nj}{7}\right)\right]\tag{3} $$

share|cite|improve this answer
There is no way when looking at $(3)$ to see that it is an integer $=0\pmod{7}$, which is extremely clear from @anon's comment to the question. – robjohn Oct 12 '11 at 23:13

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.