1
$\begingroup$

I want to compute the DFT of a vector whos entries are binomial coefficients, i.e.

$$(v)_k = \binom{N-1}{k},$$

where $k$ runs from 0 to $N-1$.

I use the DFT matrix

$$F_{k,j} := \frac{1}{\sqrt{N}}e^{-\frac{2\pi i k j}{N}}.$$

So I want to compute

$$(Fv)_\ell = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} \binom{N-1}{k}e^{-\frac{2\pi i \ell k}{N}}.$$

I don't see how to evaluate this sum. I noticed the symmetry of the binomial coefficients and the elements of the DFT matrix, but I'm not sure how to exploit it. Any suggestions?

$\endgroup$
4
$\begingroup$

You could try to apply the binomial formula with well chosen numbers, like $1$ and $\exp(-2\pi i l/N)$.

EDIT:

The binomial formula is this one: $$(a+b)^m=\sum_{k=0}^m\binom{m}{k}a^k\; b^{m-k}\, .$$

$\endgroup$
  • $\begingroup$ which formula are you referring to? $\endgroup$ – Pascal Engeler Jul 9 '13 at 12:06
  • 1
    $\begingroup$ +1 @Pascal: Binomial formula. $\endgroup$ – Jyrki Lahtonen Jul 9 '13 at 12:31
  • $\begingroup$ Yeah, sorry, of course. That was indeed a rather stupid question. Thanks a lot! $\endgroup$ – Pascal Engeler Jul 10 '13 at 7:00
1
$\begingroup$

Putting $z=\exp(-\frac{2\pi\mathbf i}N)$ you have $e^{-\frac{2\pi\mathbf ilk}N}=z^{kl}=(z^l)^k$, so you get $$ (Fv)_l = \frac1{\sqrt N}\sum_{k=0}^{N-1} \binom{N-1}ke^{-\frac{2\pi\mathbf i lk}N} = \frac1{\sqrt N}\sum_{k=0}^{N-1} \binom{N-1}k(z^l)^k = \frac{(1+z^l)^{N-1}}{\sqrt N}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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