As far as I know, the 3 steps of FFT while solving $F_nc = y$ :
Split c into c', c'' such that c' contains elements with even indexes from c and c'' contains the odd ones.
Now we have $F_mc' = y'$ and $F_mc' = y''$ where $m = n/2$
To combine $y',y''$ we use the formula
but while I was solving a problem, the solution was just: $\begin{bmatrix} y' \\ y'' \end{bmatrix} = y$
Let $n=2m$. $$F_k=\sum_{j=0}^{n-1} \omega^{kj}f_j=\sum_{j=0}^{m-1}\omega^{k(2j)}f_{2j}+\sum_{j=0}^{m-1} \omega^{k(2j+1)}f_{2j+1}=\sum_{j=0}^{m-1}(\omega^2)^{kj}(f_{2j}+\omega^kf_{2j+1})=\sum_{j=0}^{m-1}(\omega^2)^{kj}g_j$$
where $\omega$ is an $n^{th}$ root of unity. Notice that $\omega^2$ is an $m^{th}$ root of unity and we have $$\omega^{k+m}=-\omega^k.$$
This shows that the DFT on the $n$ points $f_j$ can be computed by concateneting two DFTs on the $m$ points $f_{2j}+\omega^kf_{2j+1}$ and $f_{2j}-\omega^kf_{2j+1}$ respectively, which are linear combinaisons of the even and odd elements of the initial sequence.
E.g., with $n=4$, $\omega=i$ and for $k=0,1$,
$$F_k=f_0+i^kf_1+i^{2k}f_2+i^{3k}f_3=(f_0+i^kf_1)+i^{2k}(f_2+i^kf_3) \\=(f_0+i^kf_1)+(-1)^k(f_2+i^kf_3), \\F_{k+2}=(f_0+i^{k+2}f_1)+(-1)^k(f_2+i^{k+2}f_3) \\=(f_0-i^kf_1)+(-1)^k(f_2-i^kf_3).$$