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 would like an hint to solve this equation: $\forall n\geq 1$ $$\sum_{k=0}^{2^n-1}e^{itk}=\prod_{k=1}^{n}\{1+e^{it2^{k-1}}\} \qquad \forall t \in \mathbb{R}.$$

I went for induction but without to much success; I will keep trying, but if you have an hint...

Many thanks.

share|cite|improve this question
up vote 4 down vote accepted

Hint: Note that the sum on the left is a geometric series. Without worrying yet about division by $0$, we get that the sum is $$\frac{1-e^{2^nit}}{1-e^{it}}.$$ For the induction, perhaps use the fact that $$1-e^{2^{n+1}it}=(1-e^{2^{n}it})(1+e^{2^{n}it}).$$

Once you have worked through the idea, note the following slicker but equivalent calculation. There are two cases, $e^{it}=1$ and $e^{it}\ne 1$. In the second case, multiply each side by $1-e^{it}$. Admire the beautiful collapse on both the left-hand side and the right-hand side.

For the right-hand side, which is less familiar, look for example at $$(1+a)(1+a^2)(1+a^4)(1+a^8),$$ and multiply on the left by $1-a$.

share|cite|improve this answer
Thanks you a lot. The geometric series was the key. I don't know way but I didn't see it. Many thanks again! – Kolmo Mar 20 '12 at 16:39

Fix $n\in \mathbb{N}$ and $t\in \mathbb{R}$.

  1. If $t=0 \mod 2\pi$, your equality is obviously true, for it reduces to: $$\sum_{k=0}^{2^n -1} 1 =2^n = \prod_{k=1}^n 2$$ (remember that $e^{\imath\ t}$ is $2\pi$-periodic).

  2. Now, assume $t\neq 0 \mod 2\pi$. Evaluate separately: $$\begin{split} (1-e^{\imath\ t})\ \sum_{k=0}^{2^n-1}e^{itk} &= \sum_{k=0}^{2^n-1}e^{itk} - \sum_{k=1}^{2^n}e^{itk}\\ &= 1-e^{\imath\ t\ 2^n} \end{split}$$ and: $$\begin{split} (1-e^{\imath\ t})\ \prod_{k=1}^{n} (1+e^{it2^{k-1}}) &= (1-e^{\imath\ t})\ (1+e^{\imath\ t})\ \prod_{k=2}^{n} (1+e^{it2^{k-1}})\\ &= (1-e^{\imath\ t\ 2})\ (1+e^{\imath\ t\ 2})\ \prod_{k=3}^{n} (1+e^{it2^{k-1}})\\ &= (1-e^{\imath\ t\ 4})\ (1+e^{\imath\ t\ 4})\ \prod_{k=4}^{n} (1+e^{it2^{k-1}})\\ &= \cdots\\ &= (1-e^{\imath\ t\ 2^{n-1}})\ (1+e^{\imath\ t\ 2^{n-1}})\\ &= 1-e^{\imath\ t\ 2^n}\; ; \end{split}$$ therefore you got: $$(1-e^{\imath\ t})\ \sum_{k=0}^{2^n-1}e^{itk} = (1-e^{\imath\ t})\ \prod_{k=1}^{n} (1+e^{it2^{k-1}})\; ,$$ which yields the desidered equality (because $1-e^{\imath\ t}\neq 0$).

share|cite|improve this answer
Thanks. It wasn't to hard. Gugo82? – Kolmo Mar 20 '12 at 17:04
@Kolmo: Yeap... – Pacciu Mar 20 '12 at 17:06
Un saluto dal Daje. – Kolmo Mar 20 '12 at 17:07

Let us consider the polynomial $P = \sum_{k=0}^{2^n -1 } X^k $ and $P_2 = \prod_{k=1}^{n} (1+X^{2^{k-1}})$. There exist a full combinatorial proff of this result. Hint : if you develop the second term and examine all power of $X$ you could find all the binary development of integer between $0$ and $2^{n}-1$. If you want that I complete the proof, ask me.

share|cite|improve this answer
Thanks. I am reading your comment and try to do by myself (if I am able or I'll ask for an hint). – Kolmo Mar 20 '12 at 16:46

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.