3
$\begingroup$

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 ?

|improve this question
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – robert bristow-johnson Jan 27 '15 at 18:04
  • $\begingroup$ 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. $\endgroup$ – Fat32 Jan 27 '15 at 19:44
  • $\begingroup$ @BulentS.: This is exactly what my answer is about. $\endgroup$ – Matt L. Jan 27 '15 at 19:48
  • 1
    $\begingroup$ and i concur. just adding up $N$ terms known to be $1$ is simpler than using L'Hôpital's rule. $\endgroup$ – robert bristow-johnson Jan 27 '15 at 20:01
6
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – robert bristow-johnson Jan 27 '15 at 20:00
  • $\begingroup$ @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. $\endgroup$ – Matt L. Jan 27 '15 at 20:37
  • $\begingroup$ 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? $\endgroup$ – robert bristow-johnson Jan 27 '15 at 22:13
  • $\begingroup$ @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. $\endgroup$ – Fat32 Jan 27 '15 at 22:53
  • 2
    $\begingroup$ @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. $\endgroup$ – Dilip Sarwate Jan 27 '15 at 23:26
4
$\begingroup$

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

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Matt L. Jan 27 '15 at 19:57
  • $\begingroup$ 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? $\endgroup$ – Dilip Sarwate Jan 27 '15 at 20:06
  • $\begingroup$ @DilipSarwate: According to the original question $k$ is an integer. Otherwise there would be no need for discussion. $\endgroup$ – Matt L. Jan 27 '15 at 20:35
  • 1
    $\begingroup$ 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. $\endgroup$ – robert bristow-johnson Jan 28 '15 at 15:51
  • 1
    $\begingroup$ 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 $\endgroup$ – robert bristow-johnson Jan 28 '15 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.