Obtain the $N$-point IDFT of $X(k)=\frac{3}{5-4 \cos \left(2 \pi \frac{k}{N}\right)}$

fourier analysisfourier seriesfourier transformpoisson-summation-formulasummation

I want to obtain the $N$-point IDFT of $X(k)=\frac{3}{5-4 \cos \left(2 \pi \frac{k}{N}\right)}$. My idea was to go with the discrete Poisson summation formula.
$$
x_{s}(n)=\sum_{m=-\infty}^{\infty} x(n-m N)=\frac{1}{N} \sum_{k=0}^{N-1} X(k) e^{i 2 \pi k n / N}
$$

but I didn't manage to solve it.

Any suggestions??

Best Answer

Following this answer of mine, introduce $\omega=\exp(2\pi i/N)$ and consider $$S=\sum_{k=0}^{N-1}\frac{\exp(2nk\pi i/N)}{1-2z\cos(2k\pi/N)+z^2}=\sum_{k=0}^{N-1}\frac{\omega^{kn}}{(1-z\omega^k)(1-z\omega^{-k})}$$ where $|z|\neq 1$ for simplicity (you're computing $3S/N$ at $z=2$). Now use $$\sum_{p=0}^{N-1}(z\omega^{\pm k})^p=\frac{1-(z\omega^{\pm k})^N}{1-z\omega^{\pm k}}=\frac{1-z^N}{1-z\omega^{\pm k}}$$ to get $$(1-z^N)^2 S=\sum_{k=0}^{N-1}\omega^{kn}\sum_{p=0}^{N-1}(z\omega^k)^p\sum_{q=0}^{N-1}(z\omega^{-k})^q=\sum_{p,q=0}^{N-1}z^{p+q}\sum_{k=0}^{N-1}\omega^{k(n+p-q)}.$$

The inner sum is $N$ if $n+p-q$ is a multiple of $N$ (assuming $\color{blue}{0\leqslant n<N}$, this happens iff $0\leqslant p<N-n$ and $q=p+n$, or $N-n\leqslant p<N-n$ and $q=p+n-N$).

Otherwise, this sum is $0$. And finally $$S=\frac{N}{(1-z^N)^2}\left(\sum_{p=0}^{N-n-1}z^{2p+n}+\sum_{p=N-n}^{N-1}z^{2p+n-N}\right)=\frac{N(z^n+z^{N-n})}{(1-z^2)(1-z^N)}$$ (note that $n=N$ is also acceptable here, so that the result holds for $0\leqslant n\leqslant N$).

Related Question