I am trying to learn DFT on my own. I have been struggling for a while now around understanding the concept of negative frequencies and notably what happens when $k$ is greater than $N/2$ in the equation:
$$X[k] = {1 \over N} \sum_{n=0}^{N-1} s[n] e^{-i 2 \pi {1\over N} k n}$$
This really frustrates me because I don't see it explained anywhere while it seems to be something so central and probably not that hard to explain!!! So I really need help from someone please, because I am just not progressing because of this.
So where I am at with this. I understand Euler's Formula notably the identity $e^{i\pi} = e^{-i\pi} = -1$. So far I have only being able to suspect that this is the key to my problem. So, if we have $N = 8$ for example when we get $k = {N/2}$ then we gave $k = 4$ which gives $\displaystyle e^{-i2\pi {1 \over N } 4 n} = e^{ -i\pi n} $. So I suspect something happens at this point such as a change in sign somewhere making $e^{-ixxx}$ something like $e^{ixxx}$ but I can't go any further.
Could someone please please try to help me with this, and help me going further?
Thank you very much.
Negative frequencies are best thought of as nothing more than a mathematical curiosity. Historically, Fourier series were sums of sines and cosines. But mathematicians see this as aesthetically repulsive because one must often treat the sine terms and the cosine terms differently. Also, the difference between sines and cosines is a phase shift, and it seems strange that constant phase shifts would be fundamental to this simple idea of breaking functions into periodic components.
But, as you mentioned, we can use Euler's identity $e^{i\omega}=\cos(\omega)+i\sin(\omega)$ and some basic trigonometric laws to find that $$\cos(\omega)=\frac{e^{i\omega}+e^{-i\omega}}{2},$$ $$\sin(\omega)=\frac{e^{i\omega}-e^{-i\omega}}{2i}.$$
Now, mathematically, the exponentials are much simpler, because both the sine and the cosine terms can be shoved into a single type of function. But unfortunately you have to lose the physical meaning of frequency for the negative exponents. I have heard that for some reason the frequencies above the halfway point are unreliable when they are taken from sample data. So the switch into negative frequencies for the DFT, disregarding the upper half, does not result in a loss of physical information.
(I admit I don't understand why completely, but I do know it is a theoretical problem, not just a measurement issue. The key word here is "aliasing" if you want the internet to teach you more about it.)
To answer an implicit question you asked in the middle there: you can do some translation. Euler's identity implies that $s[k]e^{2\pi i}=1$, so $s[k]e^{i(2\pi k/N)} = s[k]e^{i(2\pi k/N-2\pi)}$ which for $k<N$ will give a negative frequency in the exponent. Furthremore, for $k>N/2$ you will get a negative frequency with absolute value at most $i2\pi N/2$, so that will get you the negative values you're looking for.