# Problems computing the DFT of finite length sequence

I am having trouble finding the same answer as the solution manual for this sequence.

The problem asks to compute the DFT of $$x[n] = \begin{cases} 1 & \text{for even } n \in \{0\ldots N-1\} \\ 0 & \text{for odd } n \in \{0\ldots N-1\} \end{cases}$$

Setting up the DFT equation I agree with the solution manual $$X[k]=\sum_0^{N-1}x[n]W^{kn}_{N}=\sum_0^{\frac{N}{2}-1}W^{k2n}_{N}=\sum_0^{\frac{N}{2}-1}e^{\frac{-j2\pi k(2n)}{N}}$$

However when apply the closed form geometric series formula $$\sum_0^Na^k=\frac{1-a^{N+1}}{1-a}$$ I get $$\frac{1-e^{-j2\pi k}}{1-e^{\frac{-j2\pi k}{N}}}$$

while the solution manual says its
$$\frac{1-e^{-j2\pi k}}{1-e^{\frac{-j\pi k}{N}}}$$

Note their lower exponent does not have a 2. Could someone explain where and how the 2 goes away? Or does someone agree that the provided answer is incorrect?

This is question 8.5c from Oppenheim's Discrete-Time Signal Processing 3e.

Assuming $$N$$ even :

\begin{align} X[k] &= \sum_{n=0}^{N-1} x[n] ~ W_N^{kn} ~~~,~~~k=0,1,...,N-1\\ \\ &= \sum_{n=0}^{N/2-1} 1 ~ W_N^{k ~2n} \\ \\ &= \sum_{n=0}^{N/2-1} e^{-j 4\pi kn/N} \\ \\ & = \frac{ 1 - e^{-j \frac{4\pi k}{N}N/2 }}{ 1 - e^{-j 4\pi k/N}} \\ \\ & = \frac{ 1 - e^{-j 2\pi k}}{ 1 - e^{-j 4\pi k/N}}~~~,~~~k=0,1,...,N-1\\ \end{align}

The result equals: $$X[k] = \begin{cases}{ ~~~ N/2 ~~~ ,~~~ k = 0, N/2 \\ ~~~~~~ 0 ~~~~~ ~ ,~ ~\text{otherwise} } \end{cases}$$

• glad you posted this, I wrote an answer up and was hesitant to post it seeing that my answer didn't match either of OP's hah. – user67081 Jan 17 at 23:31
• @Fat32 thanks for the explanation. I didn't realize either was not correct. The relationship between the big N and little n keeps confusing me. based on your steps 3-4 I can see the little n is based on the summation length while the big N is based on the overall sequence length.. am I correct with this assumption? Could you also explain how you got the result to equal $N/2$? Is there some formula or assumptions you are making? – scott Jan 18 at 0:35
• @Fat32 I guess I may be misunderstanding something, for either one of them if k goes to $0$ or $N/2$ I see the exp going to either 1 (for $0$) or some other value (for $N/2$). – scott Jan 18 at 19:54
• @Fat32 I am still unsure how you are getting the final result. How does final value result in $N/2$ when it is based on the exponent? Is there some property of the exponential I am missing? For example - case $k=0$ i see it resulting in $\frac{1-e^0}{1-e^0}=\frac{1-1}{1-1}=0$? Maybe I am misunderstanding some concept about $e$? – scott Jan 18 at 20:18
• @Fat32 so after thinking a bit more, I am assuming it is connected to the fact $e$ is representing a sinusoidal signal. I will evaluate it using Euler’s equations and update. – scott Jan 18 at 20:25

Figured I'd post this since I wrote it anyway, just a confirmation of Fat32's answer.

Letting $$N' = \frac{N}{2} - 1$$ we have $$\sum_{0}^{\frac{N}{2} - 1} e^{\frac{-j2\pi k (2n)}{N}} = \sum_{0}^{N'} e^{\frac{-j2\pi k n}{(N'+1)}}$$

Then plugging in the geometric sum formula:

$$=\frac{1 - e^{\frac{-j2\pi k(N'+1)}{(N'+1)}}}{1-e^{\frac{-j2\pi k}{(N'+1)}}}=\frac{1 - e^{\frac{-j2\pi k}{1}}}{1-e^{\frac{-j2\pi k}{(N'+1)}}}$$

and finally reverting back to our original variable $$N=2(N'+1)$$ gives $$=\frac{1 - e^{\frac{-j2\pi k}{1}}}{1-e^{\frac{-j4\pi k}{N}}}$$