[proofplan]
We prove both halves of the DFT splitting identity by direct computation. For the first identity, we split the DFT sum $(\mathcal{F}_{2m}z)_\ell = \sum_{j=0}^{2m-1} \omega_{2m}^{j\ell} z_j$ into even-indexed and odd-indexed terms, then use the key relation $\omega_{2m}^2 = \omega_m$ to identify each partial sum as a length-$m$ DFT. For the second identity, we evaluate $(\mathcal{F}_{2m}z)_{\ell+m}$ similarly and use the half-period sign flip $\omega_{2m}^m = -1$ to produce the minus sign.
[/proofplan]
[step:Split the length-$2m$ DFT into even and odd index sums]
Write out the definition of the DFT for the index $\ell \in \{0, \ldots, m-1\}$:
\begin{align*}
(\mathcal{F}_{2m}z)_\ell = \sum_{j=0}^{2m-1} \omega_{2m}^{j\ell} z_j.
\end{align*}
Partition the sum into contributions from even indices $j = 2s$ (for $s = 0, \ldots, m-1$) and odd indices $j = 2s+1$ (for $s = 0, \ldots, m-1$):
\begin{align*}
(\mathcal{F}_{2m}z)_\ell = \sum_{s=0}^{m-1} \omega_{2m}^{2s\ell} z_{2s} + \sum_{s=0}^{m-1} \omega_{2m}^{(2s+1)\ell} z_{2s+1}.
\end{align*}
[/step]
[step:Identify the even-index sum as $(\mathcal{F}_m z^{(\mathrm{e})})_\ell$ using $\omega_{2m}^2 = \omega_m$]
The primitive roots of unity satisfy
\begin{align*}
\omega_{2m}^2 = e^{2 \cdot 2\pi i/(2m)} = e^{2\pi i/m} = \omega_m.
\end{align*}
Therefore $\omega_{2m}^{2s\ell} = (\omega_{2m}^2)^{s\ell} = \omega_m^{s\ell}$, and the even-index sum becomes
\begin{align*}
\sum_{s=0}^{m-1} \omega_{2m}^{2s\ell} z_{2s} = \sum_{s=0}^{m-1} \omega_m^{s\ell} z_{2s}^{(\mathrm{e})} = (\mathcal{F}_m z^{(\mathrm{e})})_\ell,
\end{align*}
where $z_s^{(\mathrm{e})} := z_{2s}$ is the $s$th component of the even subsequence $z^{(\mathrm{e})} \in \mathbb{C}^m$.
[/step]
[step:Factor the odd-index sum as $\omega_{2m}^\ell (\mathcal{F}_m z^{(\mathrm{o})})_\ell$]
For the odd-index sum, factor $\omega_{2m}^{(2s+1)\ell} = \omega_{2m}^\ell \cdot \omega_{2m}^{2s\ell} = \omega_{2m}^\ell \cdot \omega_m^{s\ell}$:
\begin{align*}
\sum_{s=0}^{m-1} \omega_{2m}^{(2s+1)\ell} z_{2s+1} = \omega_{2m}^\ell \sum_{s=0}^{m-1} \omega_m^{s\ell} z_{2s+1}^{(\mathrm{o})} = \omega_{2m}^\ell \, (\mathcal{F}_m z^{(\mathrm{o})})_\ell,
\end{align*}
where $z_s^{(\mathrm{o})} := z_{2s+1}$ is the $s$th component of the odd subsequence $z^{(\mathrm{o})} \in \mathbb{C}^m$. Combining with the even-index sum:
\begin{align*}
(\mathcal{F}_{2m}z)_\ell = (\mathcal{F}_m z^{(\mathrm{e})})_\ell + \omega_{2m}^\ell \, (\mathcal{F}_m z^{(\mathrm{o})})_\ell.
\end{align*}
This establishes the first identity.
[/step]
[step:Derive the shifted identity using the half-period sign flip $\omega_{2m}^m = -1$]
For the shifted index $\ell + m$ with $\ell \in \{0, \ldots, m-1\}$:
\begin{align*}
(\mathcal{F}_{2m}z)_{\ell+m} = \sum_{s=0}^{m-1} \omega_{2m}^{2s(\ell+m)} z_{2s} + \sum_{s=0}^{m-1} \omega_{2m}^{(2s+1)(\ell+m)} z_{2s+1}.
\end{align*}
**Even-index terms.** We compute $\omega_{2m}^{2s(\ell+m)} = \omega_m^{s(\ell+m)} = \omega_m^{s\ell} \cdot \omega_m^{sm}$. Since $\omega_m^m = e^{2\pi i} = 1$, we have $\omega_m^{sm} = (\omega_m^m)^s = 1$. Therefore
\begin{align*}
\sum_{s=0}^{m-1} \omega_{2m}^{2s(\ell+m)} z_{2s} = \sum_{s=0}^{m-1} \omega_m^{s\ell} z_{2s} = (\mathcal{F}_m z^{(\mathrm{e})})_\ell.
\end{align*}
**Odd-index terms.** We compute $\omega_{2m}^{(2s+1)(\ell+m)} = \omega_{2m}^{\ell+m} \cdot \omega_{2m}^{2s(\ell+m)} = \omega_{2m}^{\ell+m} \cdot \omega_m^{s\ell}$ (using $\omega_m^{sm} = 1$ as above). The twiddle factor decomposes as
\begin{align*}
\omega_{2m}^{\ell+m} = \omega_{2m}^\ell \cdot \omega_{2m}^m = \omega_{2m}^\ell \cdot e^{2\pi i m/(2m)} = \omega_{2m}^\ell \cdot e^{i\pi} = -\omega_{2m}^\ell.
\end{align*}
Therefore
\begin{align*}
\sum_{s=0}^{m-1} \omega_{2m}^{(2s+1)(\ell+m)} z_{2s+1} = -\omega_{2m}^\ell \sum_{s=0}^{m-1} \omega_m^{s\ell} z_{2s+1} = -\omega_{2m}^\ell \, (\mathcal{F}_m z^{(\mathrm{o})})_\ell.
\end{align*}
Combining the even and odd contributions:
\begin{align*}
(\mathcal{F}_{2m}z)_{\ell+m} = (\mathcal{F}_m z^{(\mathrm{e})})_\ell - \omega_{2m}^\ell \, (\mathcal{F}_m z^{(\mathrm{o})})_\ell.
\end{align*}
This establishes the second identity.
[guided]
The crucial identity driving the sign change is $\omega_{2m}^m = e^{i\pi} = -1$. Geometrically, $\omega_{2m}$ is the primitive $2m$th root of unity sitting at angle $\frac{2\pi}{2m} = \frac{\pi}{m}$ on the unit circle. Raising it to the $m$th power rotates to angle $\frac{m\pi}{m} = \pi$, which is exactly $-1$.
This single sign flip is what makes the second identity differ from the first by only a minus sign in front of the odd-part DFT. In the FFT algorithm, this means the same two length-$m$ DFTs $\mathcal{F}_m z^{(\mathrm{e})}$ and $\mathcal{F}_m z^{(\mathrm{o})}$ are reused for both the first half ($\ell = 0, \ldots, m-1$) and the second half ($\ell + m = m, \ldots, 2m-1$) of the output. The only difference is the sign of the twiddle factor $\omega_{2m}^\ell$ — add for the first half, subtract for the second. This "butterfly" structure is the source of the FFT's efficiency.
Let us verify the even-index computation for the shifted case more carefully. We have $\omega_{2m}^{2s(\ell+m)} = \omega_m^{s\ell} \cdot \omega_m^{sm}$. The factor $\omega_m^{sm} = (e^{2\pi i/m})^{sm} = e^{2\pi i s} = 1$ for any integer $s$. So the even-index sum at position $\ell + m$ is identical to the even-index sum at position $\ell$. For the odd-index sum, the extra factor of $\omega_{2m}^m = -1$ flips the sign, giving the result.
[/guided]
[/step]
