Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to find the discrete Fourier transform of $$y_k=\left[k-\frac{m-1}{2}\right]^{2},$$ but I am not sure of the step by step for going about this computation.

how is the first step??

thank you very much!!

share|cite|improve this question
Do the square brackets indicate a rounding function, or are they just being used as parentheses? – anon Jun 18 '12 at 21:23
@nname: By removing the equations from your question, you made it impossible to understand. That constitutes vandalism. If you do something like that again, you may be suspended. – Zev Chonoles Jun 18 '12 at 22:42
up vote 4 down vote accepted

I assume you want a DFT of $(y_0,y_1,\cdots,y_{n-1})$ given $n$. First write out the FT and then expand:

$$\begin{array}{c l}\widehat{y}_r & =\sum_{k=0}^{n-1}\left(k-\frac{m-1}{2}\right)^2\exp\left(-2\pi i\frac{kr}{n}\right) \\ & = \left(\sum_{k=0}^{n-1}k^2 \big(e^{-2\pi i r/n}\big)^k\right)-(m-1)\left(\sum_{k=0}^{n-1}k\big(e^{-2\pi i r/n}\big)^k\right)+\left(\frac{m-1}{2}\right)^2\left(\sum_{k=0}^{n-1}\big(e^{-2\pi i r/n}\big)^k\right).\end{array}$$

Now some tricks come in handy. First, the geometric sum formula:

$$\sum_{k=0}^{n-1} z^k=\frac{z^n-1}{z-1}.$$

Differentiating this and then multiplying by $z$ gives:

$$\sum_{k=0}^{n-1} kz^{k}=\frac{(n-1)z^{n+1}-nz^n+z}{(z-1)^2}. \tag{*}$$

Plugging in $z=e^{-2\pi i r/n}$ will give the middle term of our expression, and the geometric sum formula itself works on the last term (it's zero unless $r=0$, in which case it's a sum of $1$'s), but what about the first term? Differentiate $(*)$ and multiply by $z$ again to get another formula...

share|cite|improve this answer
I'm assuming the brackets are just being used as parentheses. – anon Jun 18 '12 at 21:31
thank you for replie. do you know from a source by which they show step by step how to solve fourier transforms? thank you very much!! – nanme Jun 18 '12 at 22:49
@nanme: You mean compute the Fourier transforms of various functions? There are many sources, though I'm not familiar with what's good for DFT's in particular (maybe a signal analysis text). Note that the formulas and derivations needed for this problem are given or hinted at in my answer - if you need further clarification don't be shy. – anon Jun 19 '12 at 20:25

You are asking how to find the DFT of sequence of the form $y(k) = k^2 + bk + c$ for $k=0,1,2,\ldots$, and with $b$ and $c$ both constants. The DFT is a linear operator, so the DFT of the above is simply $\mathrm{DFT}(k^2) + b \cdot \mathrm{DFT}(k) + \mathrm{DFT}(c)$. There are countless derivations of these three DFTs available through google'ing.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.