# Confused With using Fast Fourier Transformation for solving equations

As far as I know, the 3 steps of FFT while solving $$F_nc = y$$ :

1. Split c into c', c'' such that c' contains elements with even indexes from c and c'' contains the odd ones.

2. Now we have $$F_mc' = y'$$ and $$F_mc' = y''$$ where $$m = n/2$$

3. 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).$$

• sorry but my question is that I saw 2 ways of solving this question and they don't give the same result. Which one of them is the correct one ? :| – Mohamad Ziad Alkabakibi Apr 9 at 7:35