# When has this sequence a triangular shape?

Can someone explain to me why y[n] has a triangular shape? From what I have found, there is a specific range $n_0$ where y[n] is triangular. But right now I have no clue where to start.

$^2$ Search in a table of Fourier transform properties

-
What's $u$?${}$ – J. M. May 16 '11 at 0:29
The only explanation I can think is you are doing something wrong. The inverse transform of the direct transform is the original sequence. – leonbloy May 16 '11 at 0:47
u should be the step function. – madmax May 16 '11 at 7:57
@leonbloy Yes, i was thinking the same but the question is like that: Considering the properties of the DFT, explain why the sequence y[n] has in general a triangular shape. – madmax May 16 '11 at 8:02

A simple way to see this: taking the square of a Fourier transform is just multiplying its Fourier transform with itself. Now, taking the inverse transform of a product of two Fourier transforms is the same as convolving the two original functions. Here you are convolving a step function with itself. Now, think about how convolutions work and it should be evident that the result is a triangle function. But if you don't see it, just work out the convolution product of two step functions.

EDIT: Here's a detailed worked out solution. Using the definition from wikipedia for the DFT:

$$\text{DFT}(x[n])=\sum_{n=0}^{N-1}(u[n]-u[n-n_0])e^{-\frac{2\pi i}{N}k n} = \sum_{n=0}^{n_0-1}e^{-\frac{2\pi i}{N}k n} \; .$$

If you multiply this DFT with itself, you get the following sum

$$(\text{DFT}(x[n]))^2= \left(\sum_{n=0}^{n_0-1}e^{-\frac{2\pi i}{N}k n}\right)\left(\sum_{m=0}^{n_0-1}e^{-\frac{2\pi i}{N}k m}\right) = \sum_{n=0}^{n_0-1}\sum_{m=0}^{n_0-1}e^{-\frac{2\pi i}{N}k (m+n)} \; .$$

With a change of variables $t=m+n$, you can now write this as

$$(\text{DFT}(x[n]))^2 = \sum_{t=0}^{2(n_0-1)} z[t] e^{-\frac{2\pi i}{N}k t} \; .$$

where $z[t]$ is

$$z[t]=\begin{cases}1, \text{ if } t=0=0+0,\\ 2, \text{ if } t=1=1+0=0+1,\\ 3, \text{ if } t=2=2+0=1+1=0+2,\\ \ldots\\ 2, \text{ if } t=2n_0-3=n_0-1+n-0-2=n_0-2+n_0-1,\\ 1, \text{ if } t=2n_0-2=n_0-1+n_0-1,\\ \end{cases}$$

which is a triangular function. Note however that if $2(n_0-1)\geq N$, then because of periodicity, $z[t]\neq y[t]$. You'll have to add the $z[t]$'s corresponding to a same frequency to obtain the correct expression for $y[t]$, since $y[t]$ is only defined over the range $[0,N-1]$ just like $x[n]$.

So the range they are talking about in the question is $0\leq2(n_0-1)<N$.

-
The breadth of the interval over which the function is triangular should be twice $n_0$. So, on the interval $[-n_0,n_0]$. Outside of this interval, the convolution product will be zero since the step function and the shifted step function will not overlap. – Raskolnikov May 20 '11 at 19:02
About the zeros, they might have meant the values at the extremities of the interval, which are zero (if $n_0<N/2$). If you choose to work on the open interval $]-n_0,n_0[$, you don't include them. To your second question, I'd say yes. Also, since you are working with the discrete transform, your interval is capped off at $0$ and $N$, So if $n_0>N/2$, I think you'll get a triangle as well, but it will not start at height $0$. If $n_0=N$ You'll get a constant function. – Raskolnikov May 21 '11 at 11:30
@madmax: I'm kind of working with a continuous Fourier transform in my mind, so I forget about the differing details in the case of a DFT, but the principles are really the same. I'll add a detailed calculation to make thing clear. – Raskolnikov May 22 '11 at 10:24
You got your $x$ wrong. When $N=25$ and $n_0=22$, the last three values at $22, 23 \text{ and } 24$ are $0$, all the others are $1$. – Raskolnikov May 22 '11 at 21:14
First, following the definition in the OP, your range should be n=0:N-1. Second, there is indeed always a "triangle", but the base level is not always 0, and I suppose the question doesn't count these as real "triangles". But I have to say that is a bit silly. I didn't write the question however. – Raskolnikov May 23 '11 at 8:49