### FAST FOURIER TRANSFORM:

In the decimation in time FFT a big DFT is build from smaller ones. The assumption is $$N = 2^m$$ with $$N$$ being the number of sampled points. The sampled points (in the time domain), i.e. $$x[n]$$ are separate into even and odd-indexed sequences. $$k$$ corresponds to the harmonic number or frequency parameter:

Remembering that $$\large\color{blue}{\large W_N \equiv e^{-i\frac{2\pi}{N}}}$$ corresponds to the twiddle factor:

$\large X[k]=\sum_{n=0}^{N-1}\,x[n]\,W_N^{kn}=\sum_{n\text{ even}}\,x[n]\,W_N^{kr}\,+\,\sum_{n\text{ odd}}\,x[n]\,W_N^{kr}$

where $$n = 2r$$ for even indices, and $$n = 2r +1$$ for odd indices, and $$r = 0,1,\cdots,\frac{N}{2}-1.$$

So we can re-write the eqution as:

\large\begin{align}\large X[k]&=\sum_{r=0}^{\frac{N}{2}-1}\,x[2r]\,W_N^{k2r} + \sum_{r=0}^{\frac{N}{2}-1}\,x[2r+1]\,W_N^{k(2r+1)}\\[2ex]\ &= \sum_{r=0}^{\frac{N}{2}-1}\,x[2r]\,W_N^{k2r} + \sum_{r=0}^{\frac{N}{2}-1}\,x[2r+1]\,W_N^{k}W_N^{k2r}\\[2ex] &=\sum_{r=0}^{\frac{N}{2}-1}\,x[2r]\,W_N^{k2r} +W_N^{k} \sum_{r=0}^{\frac{N}{2}-1}\,x[2r+1]\,W_N^{k2r}\\[2ex] &=\sum_{r=0}^{\frac{N}{2}-1}\,x[2r]\,(W_N^2)^{kr} +W_N^{k} \sum_{r=0}^{\frac{N}{2}-1}\,x[2r+1]\,(W_N^2)^{kr}\\[2ex] &\underset{*}= \sum_{r=0}^{\frac{N}{2}-1}\,x[2r]\,W_{N/2}^{kr} +W_N^{k} \sum_{r=0}^{\frac{N}{2}-1}\,x[2r+1]\,W_{N/2}^{kr}\\[2ex] &\underset{**}= X_e[k] + W_N^k\,X_o[k] \end{align}

$$*$$ because $$\color{blue}{W_N^2=e^{-i\frac{2\dot2\pi}{N}}=e^{-i\frac{2\pi}{N/2}}=W_{N/2}}$$

$$**$$ the sum of two $$N/2$$ point DFTs.

But $$k$$ runs from 0 to $$N-1$$ while there are only $$N/2$$ odd numbers and $$N/2$$ even numbers. So how can it be… Let’s try with an $$8$$-point DFT:

For $$k=0$$:

\begin{align}X[0]&=\sum_{r=0}^{3}\,x[2r]\,W_{4}^{0r} +W_8^{0} \sum_{r=0}^{3}\,x[2r+1]\,W_{4}^{0r}\\[2ex] &=\sum_{r=0}^{3}\,x[2r] +W_8^{0} \sum_{r=0}^{3}\,x[2r+1]\\[2ex] &=X_e[0] + X_o[0] \end{align}

For $$k=1$$:

\begin{align}X[1]&=\sum_{r=0}^{3}\,x[2r]\,W_{4}^{1r} +W_8^{1} \sum_{r=0}^{3}\,x[2r+1]\,W_{4}^{1r}\\[2ex] &=X_e[1] + W_8^1\,X_o[1] \end{align}

$$\vdots$$

For $$k = 4$$, though, this reasoning, runs into a “problem” because summarizing the corresponding expression as a sum of DFT of even and odd numbers, such as

\begin{align}X[\color{red}{4}]&\overset{?}=X_e[\color{red}{4}]+W_8^4\,X_o[\color{red}{4}]\tag{1}\\[2ex] &\overset{?}=\sum_{r=0}^{\color{red}{3}}\,x[2r]\,W_{4}^{\color{red}{4}r} +W_8^{4} \sum_{r=0}^{\color{red}{3}}\,x[2r+1]\,W_{4}^{\color{red}{4}r} \end{align}

makes apparently no sense, since $$k$$ in DFT runs from $$0,1,2,\cdots,r-1=3$$.

However,

$\large W_4^{4r}=e^{-i\frac{2\pi}{4}4r}=1=W_{4}^{0r}$.

Hence $$X[\color{red}{4}]= X[0]$$.

What about $$X[5]$$… well

\begin{align}\large W_4^{5r} &= e^{-i\frac{2\pi}{4}5r}\\[2ex] &= e^{-i\frac{2\pi}{4}4r}\,e^{-i\frac{2\pi}{4}r}\\[2ex] &= e^{-i\frac{2\pi}{4}r}\\[2ex] &= W_4^{1r} \end{align}

Going back to Eq. $$1$$:

$X[\color{red}{4}]=X_e[\color{red}{4}]+W_8^4\,X_o[\color{red}{4}]=X_e[\color{red}{0}]+W_8^1\,X_o[\color{red}{0}]$

$X[\color{red}{5}]=X_e[\color{red}{5}]+W_8^5\,X_o[\color{red}{5}]=X_e[\color{red}{1}]+W_8^5\,X_o[\color{red}{1}]$

$X[\color{red}{6}]=X_e[\color{red}{6}]+W_8^6\,X_o[\color{red}{6}]=X_e[\color{red}{2}]+W_8^6\,X_o[\color{red}{2}]$

\begin{align}X[\color{red}{7}]&=X_e[\color{red}{7}]+W_8^7\,X_o[\color{red}{7}]=X_e[\color{red}{3}]+W_8^7\,X_o[\color{red}{3}]\\[2ex] &=\underset{X_e[3]}{\underbrace{\sum_{r=0}^{\color{red}{3}}\,x[2r]\,W_{\color{blue}{4}}^{\color{red}{3}r}}} +W_8^{7} \underset{X_o[3]}{\underbrace{\sum_{r=0}^{\color{red}{3}}\,x[2r+1]\,W_{\color{blue}{4}}^{\color{red}{3}r}}} \end{align}

Explaining the plot in this youtube video: