# Complex number: equation

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.

-

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$.

-
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$).

-
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.

-
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