2
$\begingroup$

I am solving a question from book in which I have to use summation. It is as follows:

$$ \frac{1}{10}\sum_{n=0}^{9} e^{-jk\omega_0n} $$ The value of $\omega_0$ is $\frac{2\pi}{10}$. What I have done so far is:

$$ \frac{1}{10} \left(\frac{1-e^{-9jk\frac{2\pi}{10}}.e^{jk\frac{2\pi}{10}}} {1-e^{-jk\frac{2\pi}{10}}}\right)$$

After this step I am stuck and can not figure out the next step?

|improve this question
$\endgroup$
  • $\begingroup$ I believe the solution can be found by considering the fact that the exponential expressions represent complex numbers which can be intuitively added in the complex plane. Hint: what is the sum of $e^{0} + e^{-j\pi}$? $\endgroup$ – applesoup Nov 13 '18 at 13:35
9
$\begingroup$

This sum appears quite often in DSP.

\begin{align} \sum_{n=0}^{N-1} \exp(-j\alpha n) &\stackrel{(a)}{=} \frac{1- \exp(-j\alpha N)}{1 - \exp(-j\alpha )}\\ &= \frac{e^{-j\alpha N/2}(e^{+j\alpha N/2}- e^{-j\alpha N/2})}{e^{-j\alpha /2}(e^{+j\alpha /2}- e^{-j\alpha /2})}\\ &\stackrel{(b)}{=} e^{-j\frac{\alpha}{2}(N-1)} \frac{\sin(N\alpha/2)}{\sin(\alpha/2)} \end{align} where the last step $(b)$ comes from identity $e^{+j\theta}-e^{-j\theta} = 2j\sin(\theta)$ and be careful at $(a)$ as Matt's comment.

Substitute $\alpha=k\omega_0=k\frac{2\pi}{N}$, $\sin(N\alpha/2)=\sin(k\pi)=0$ if $k\in\mathbb{Z}$ hence so is the sum.

Update for $\alpha=0$

It is trivial that $\exp(-j\alpha n) \stackrel{\alpha=0}{=} 1$ then the sum equals $N$.

It can be thought as the case of the final result after $(b)$ when $\alpha \to 0$ then $$e^{-j\frac{\alpha}{2}(N-1)} \frac{\sin(N\alpha/2)}{\sin(\alpha/2)} \stackrel{\alpha \to 0}{\to} N$$ where the limit is evaluated by L'Hôpital's rule.

Further interesting discussion can be found in Laurent Duval's answer.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Note that technically speaking your first equation is not correct for $\alpha =0$ (i.e., $k=0$ in the OP's example), because you're dividing by zero; luckily, in the final formula, $\alpha=0$ leads to the correct result if taken as a limit. That's also why most people never realize / don't care. $\endgroup$ – Matt L. Nov 13 '18 at 14:09
  • $\begingroup$ it's true @MattL. $\endgroup$ – AlexTP Nov 13 '18 at 14:11
  • 1
    $\begingroup$ @MattL. Is it really luckily or will it always be the same when taken as a limit ? Are there any such summation formulas (in the context of DSP) that you know which do not equate to their L'Hopital limits at the 0/0 condition ? $\endgroup$ – Fat32 Nov 13 '18 at 21:31
  • 1
    $\begingroup$ I would argue that the OP did not claim $k$ was integer. $\endgroup$ – AlexTP Nov 14 '18 at 12:18
  • 1
    $\begingroup$ @AlexTP: Engineers using $k$ as a continuous (real) variable shouldn't be trusted ;) And, what is more, that formula looks very much like a DFT of a quite simple sequence, in which case $k$ would indeed be integer. But, you're right, who am I to assume anything that is not explicitly stated in the question!? $\endgroup$ – Matt L. Nov 14 '18 at 18:15
3
$\begingroup$

As a good answer has been given by @AlexTP, I'll go from the detail to a larger picture.

Although the "De L'Hospital's rule" seems attractive, it should be handled with a lot of care (see my answer to Why does L'Hopital's rule fail in this case?), because it requires somehow strong conditions!

I do recommend to use weaker conditions instead, when one can. And with sines of positive arguments around zero $(0\le x\le\epsilon)$, luckily, one can the standard simple bounds:

$$ x(1-x^2/6) \le \sin(x) \le x$$

which suffice to bound the sine ratio $\frac{\sin(N\alpha/2)}{\sin(\alpha/2)}$ as $\alpha \to 0$ with $N$ given. More precisely, for both $0\le \alpha/2\le\epsilon$ and $0\le N\alpha/2\le\epsilon$, we have

$$ N\alpha/2(1-(N\alpha/2)^2/6) \le \sin(N\alpha/2) \le N\alpha/2$$ and $$ \frac{1}{\alpha/2} \le \frac{1}{\sin(\alpha/2)} \le \frac{1}{\alpha/2(1-(\alpha/2)^2/6)}$$

thus

$$ N(1-(N\alpha/2)^2/6) \le \frac{\sin(N\alpha/2)}{\sin(\alpha/2)} \le \frac{N}{(1-(\alpha/2)^2/6)}\,,$$ whose central term thus tends to $N$ as $\alpha \to 0_+$. And you can plug it into AlexTP solution.

What is important here is that the underlying function of $k$ (just suppose $k \in \mathbb{R}$) is obviously continuous, as it is a finite sum of ($N=10$) continuous functions $f_n(k)=\exp(-jk w_0 n)$ (this could not work with infinite sums, as an infinite sum of continuous functions might be discontinuous, especially if the convergence is not uniform).

So, you can conveniently use the geometric sum formula anywhere it holds (with a non-zero denominator), and just use the limit (as the function IS continuous) otherwise.

This sum of an exponential geometric series is important: it is the discrete equivalent to the Fourier transform of a continuous rectangular window. The former yields a sinc, a cardinal sine. Your formula, for a discrete rectangular window, yield a (phased) discrete sinc called aliased sinc (asinc) or periodized sinc (psync), with details on the JOS website signal processing site.

|improve this answer
$\endgroup$
  • $\begingroup$ [off topic] adding an infinitely many continuous functions can produce a discontinuous resultant ? Such as the ideal LPF frequency response. But according to mathematical induction, it should be continuous too? So why is mathmeatical induction failing here? Do you know conditions on which mathematical induction can be applied or not? According to m.induction, if sum of two continuous functions are continuous -which is-, then the sum of N cont.func. will be also continuous for all N. So why is the contradiction ? $\endgroup$ – Fat32 Nov 14 '18 at 0:03
  • $\begingroup$ From my forgotten past, if the convergence is uniform, then the resulting function is continuous as well. The set of natural number $\mathbb{N}$ does not contains infinity. Another example: a finite sum of rationals is rational. But $1-\frac{1}{3}+ \frac{1}{5} - \cdots \to \pi/4$. $\endgroup$ – Laurent Duval Nov 14 '18 at 7:43
  • $\begingroup$ Second thought: it is more about the notion of limit. Continuity does not always hold under limits. Infinite sums are special cases of limits $\endgroup$ – Laurent Duval Nov 14 '18 at 7:46
  • 1
    $\begingroup$ @Fat32, This is the very question that spawned Real Analysis (my least favorite math courses). There is not a failure of induction. The limit case is not part of the sequence. The limit of a sequence of continuous functions can be a discontinuous functions, but the limit is never reached it is only approached. It's one of those epsilon and delta arguments. $\endgroup$ – Cedron Dawg Nov 14 '18 at 13:17
  • 1
    $\begingroup$ Infinity can be treated, as in Non-standard analysis, but it usually requires an additional set of axioms $\endgroup$ – Laurent Duval Nov 14 '18 at 16:01

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.