# DFT of binomial coefficients

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?

You could try to apply the binomial formula with well chosen numbers, like $1$ and $\exp(-2\pi i l/N)$.
The binomial formula is this one: $$(a+b)^m=\sum_{k=0}^m\binom{m}{k}a^k\; b^{m-k}\, .$$
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}.$$