# Deriviation of the “Twiddle Sum” property

I can't seem to understand how to derive the "twiddle sum" property:

$$\sum_{n=0}^{N-1}W_{N}^{kn}=N \ \delta[k\bmod N]$$ where $$W_{N} \triangleq e^{\frac{j 2 \pi }{N}}$$ and $$\delta[n] \triangleq \begin{cases} 1 & \text{if } n=0 \\ 0 & \text{otherwise} \end{cases}$$

I've tried doing the following:

\begin{align} \sum_{n=0}^{N-1}W_{N}^{kn} & = \sum_{n=0}^{N-1}e^{\frac{j 2 \pi k n}{N}} \\ & = \sum_{n=0}^{N-1} \left( e^{\frac{j 2 \pi k}{N}} \right)^n \\ & = \frac{1 - \left( e^{\frac{j 2 \pi k}{N}} \right)^N}{1 - e^{\frac{j 2 \pi k}{N}}} \\ & \\ & = \frac{1 - e^{j 2 \pi k}}{1-e^{\frac{j 2 \pi k}{N}}} \\ & \\ & = \begin{cases} ?? & \text{if } k=mN \quad\quad m\in \mathbb{Z} \\ 0 & \text{otherwise} \quad k \in \mathbb{Z} \end{cases} \\ \end{align}

It seems I'm missing an $N$ before the delta, have I done a mistake ?

• i polished up the math usage a little. there were problems using the same $n$ for the summation and as an argument (which should have been $k$). anyway, you need to figger out what the $??$ is. i might suggest L'Hôpital's rule. – robert bristow-johnson Jan 27 '15 at 18:04
• Even though L'Hopital's rule yields the required answer as N, as of my personal opinion, it will be much simpler to consider the very top sum for k=mN as a sum of N many 1's which is N. – Fat32 Jan 27 '15 at 19:44
• @BulentS.: This is exactly what my answer is about. – Matt L. Jan 27 '15 at 19:48
• and i concur. just adding up $N$ terms known to be $1$ is simpler than using L'Hôpital's rule. – robert bristow-johnson Jan 27 '15 at 20:01

The most straightforward way to see this is to note that for $k=mN$

$$W_N^{kn}=e^{j2\pi mnN/N}=e^{j2\pi mn}=1$$

So the sum for the case $k=mN$ is simply

$$\sum_{n=0}^{N-1}1=1+1+\ldots+1=N$$

Note that the solution using L'Hopital's rule is a bit dubious because for $k=mN$ the formula for the geometric series is not valid because the terms are all equal to one (note the $r\neq 1$ condition in the link above). So you arrive at an expression that is only valid for $k\neq mN$, and then you somehow massage it into a solution that also works for $k=mN$, but this is bad math, even for engineers.

• yeah, yer right, Matt. it would be easier to just add it up. the use of L'Hôpital's rule isn't invalid IMO since it is a $\frac00$ sorta limit, just harder than necessary to get the answer. – robert bristow-johnson Jan 27 '15 at 20:00
• @robertbristow-johnson: But the $\frac{0}{0}$ sorta limit comes from a formula which is invalid in the first place. The formula for the geometric series only works if the terms are not all equal to 1. – Matt L. Jan 27 '15 at 20:37
• hunh?? this is valid $$\sum\limits_{n=0}^{N-1} a^n = \frac{1 - a^N}{1-a}$$ even when $a=1$, no? you still gotta do L'Hôpital to it (if $a = 1$) because the bottom and top are going to zero (at different rates) as $a \rightarrow 1$. no? – robert bristow-johnson Jan 27 '15 at 22:13
• @robert bristow-johnson: yes I think you can analyse that equality in the limiting sense as when $\lim_{a \to 1}$ in which case since a will never be 1, the equality will hold and you can apply L'Hopital's rule to recover the indeterminate quotient... But this is more intuitive than being formal. I guess a rigorous justification for the interchange of orders of limits is beyond the scope of ordinary engineers. – Fat32 Jan 27 '15 at 22:53
• @robertbristow-johnson No, $\displaystyle\sum\limits_{n=0}^{N-1} a^n = \frac{1-a^N}{1-a}$ is not valid when $a=1$. What is true always is that $$\sum\limits_{n=0}^{N-1}a^n-a\sum\limits_{n=0}^{N-1}a^n= 1-a^N.\tag{1}$$You _can_ always write the LHS as $(1-a)\sum\limits_{n=0}^{N-1}a^n$, but when $a=1$, you cannot divide both sides of $(1)$ by $(1-a)$ to conclude that $$\sum\limits_{n=0}^{N-1} a^n = \frac{1 - a^N}{1-a}$$ because you are dividing by $0$. So, your starting point for application of L'Hopital's rule is invalid. – Dilip Sarwate Jan 27 '15 at 23:26

The key is in the last step of your work:

$$\frac{1 -e^{j2\pi k}}{1-e{\frac{j2\pi k}{N}}}$$

If $k$ is some integer multiple of $N$, then the exponents in the numerator and denominator are both some integer multiple of $j2\pi$. In this case, both exponential functions are equal to 1, meaning that the expression above is equal to $\frac{0}{0}$ for $k$ an integer multiple of $N$. That's an indeterminate form, and is not equal to one in the general case as you assumed.

Instead, we evaluate the limit of the above expression as $k \to mN$, where $m$ is an integer. We can do so using L'Hopital's rule, as RBJ pointed out in the comment above.

$$\lim_{k \to mN} \frac{1 -e^{j2\pi k}}{1-e{\frac{j2\pi k}{N}}} = \lim_{k \to mN} \frac{\frac{d}{dk} \left(1 -e^{j2\pi k}\right)}{\frac{d}{dk} \left(1-e{\frac{j2\pi k}{N}}\right)}$$

$$= \frac{j2\pi e^{j2\pi k}}{\frac{j2\pi}{N} e^{j2\pi k}} = N$$

There's your missing factor of $N$.

• The formula you start with is actually not valid because it only works for a geometric series when the terms are not all equal to $1$, which they are for $k=mN$. See also my answer. – Matt L. Jan 27 '15 at 19:57
• So is $k$ supposed to an arbitrary real number or is it restricted to being an integer when L'Hopital's rule is being invoked? – Dilip Sarwate Jan 27 '15 at 20:06
• @DilipSarwate: According to the original question $k$ is an integer. Otherwise there would be no need for discussion. – Matt L. Jan 27 '15 at 20:35
• what i am saying is that $$\lim_{a \to 1}\frac{1-a^N}{1-a} = N$$ only proves (in an inefficient manner) that $$\sum\limits_{n=0}^{N-1} 1 = \lim_{a \to 1} \sum\limits_{n=0}^{N-1} a^n = N$$ . dunno why that is controversial. – robert bristow-johnson Jan 28 '15 at 15:51
• okay, two things (similarly related): first of all, for a finite N, there is absolutely no reason that $$\sum\limits_{n=0}^{N-1} a^n = \frac{1-a^N}{1-a}$$ is not valid for $|a|>1$. second, even for $a=1$, of course you cannot simply divide by zero. but this is what we used to call a "removable singularity" and the formula is valid if you apply L'Hôpital's rule. i'm not saying that it's the efficient method (simply adding up $N$ terms of $1$ is much simpler), but it's not invalid – robert bristow-johnson Jan 28 '15 at 15:59