Let $v = [v_0, v_1, \dots, v_{n−1}]^T$ is the Discrete Fourier Transformation, $V = [V_0, \dots, V_{n-1}]^T $. Define $w = [w_0, w_1, \dots, w_{2n−1}]^T$ where $v_k =w_k$ for $0 \leq k \leq n−1$ and $w_k =0$ for $n \leq k \leq 2n−1$. Let $W_k$ is the kth discrete transform of $w$. Show that
$$ W_k= \begin{cases} V_{k/2} & \text{$k$ is even} \\ \frac{2}{N}\sum^{N-1}_{n=0}V_{n}/(1-e^{\frac{i\pi}{N}(2m-k)}) & \text{$k$ is odd} \\ \end{cases} $$
In trying to solve is I have deconstructed $W_k$ in to $$W_{2d}= \sum^{2N-2}_{n=0}w_ne^{j\frac{2\pi}{2N}2dn}$$ $$= \sum^{2N-2}_{n=0}w_ne^{j\frac{2\pi}{N}dn}$$ and by $v$ being half the entries of w and the rest being zero we have $$= \sum^{N-1}_{n=0}v_ne^{j\frac{2\pi}{N}dn}= V_d$$ So that part is done. The second part has been the biggest difficulty. I have worked backwards from the desired solution and forwards. I do not know if I'm going in the right direction for this proof. If $k=2d+1$ $$W_{2d+1}= \sum^{2N-2}_{n=0}w_ne^{j\frac{\pi}{N}(2d+1)n}$$ $$= \sum^{2N-2}_{n=0}w_ne^{j\frac{\pi}{N}(2d+1)n}$$ $$= \sum^{N-1}_{n=0}v_ne^{j\frac{\pi}{N}(2d+1)n}$$ To get the desired result, I multiplied both sides some $e^{\frac{i\pi k}{N}}-e^{\frac{i2\pi kd}{N}}$ and taking another some on each side sum. But I feel like I'm missing something, any hint or nudge in the right direction. Or article I can read looking at something similar would very much help. Thank you
I found a possible solution. I'll leave this up here for anyone else with a similar question.
We have $\hat y_k$ is the discrete fourier transformed vector $kth$ entry for some $y$ vector and $\hat x_k$ is the $kth$ entry for some discrete fourier transformed vector x. Our plan is to first solve directly to find $k$ even then use this solution to find $k$ odd with an inverse DFT. We have that $$\hat y_k= \sum^{2N-1}_{n=0}y_ne^{j\frac{2\pi}{2N}nk}$$ if $n=2d$ $$\hat y_{2d}= \sum^{2N-1}_{n=0}y_{n}e^{j\frac{2\pi}{2N}2dn}= \sum^{2N-1}_{n=0}y_{n}e^{j\frac{4\pi}{2N}dn}= \sum^{2N-1}_{n=0}y_{n}e^{j\frac{2\pi}{N}dn}$$ $y_{n}=x_{n}$ for $0\leq k \leq n-1$ and otherwise $y_{n}=0$ so $$\sum^{2N-1}_{n=0}y_{n}e^{j\frac{2\pi}{N}dn}= \sum^{N-1}_{n=0}x_{n}e^{j\frac{2\pi}{N}dn}=\hat x_{d}$$ This solves the first part of the solution. We now solve for when $n$ is odd.\ $$y_k =\frac{1}{2N}\sum^{2N-1}_{n=0}\hat y_n e^{-j \frac{\pi n k}{N}}$$ splitting the sums into odds and evens $$=\frac{1}{2N}(\sum^{N-1}_{d=0}\hat y_{2d}e^{-j\frac{2\pi kd}{N}})+\frac{1}{2N}(\sum^{N-1}_{d=0}\hat y_{2d+1}e^{-j\frac{\pi}{N}(2d+1)k})$$ from the even values found of $k$ $y_k=\hat x_{k/2}$ , $$=\frac{1}{2N}(\sum^{N-1}_{d=0}\hat x_{d}e^{-j\frac{2\pi kd}{N}})+\frac{1}{2N}(\sum^{N-1}_{d=0}\hat y_{2d+1}e^{-j\frac{\pi}{N}(2dk)})e^{-j\frac{\pi}{N}k}$$ this gives us the following sum $$y_k=\frac{1}{2} x_k +\frac{1}{2N}(\sum^{N-1}_{d=0}\hat y_{2d+1}e^{-j\frac{\pi}{N}(2dk)})e^{-j\frac{\pi}{N}k}$$ which implies $$(y_k-\frac{1}{2} x_k )e^{j\frac{\pi}{N}k}=\frac{1}{2N}(\sum^{N-1}_{d=0}\hat y_{2d+1}e^{-j\frac{\pi}{N}(2dk)})$$ Multiplying both sides by $e^{\frac{2\pi k dj}{N} }$ and summing both sides to $k=N-1$, with the intent of yielding a specific $d$. $$\sum^{N-1}_{k=0}e^{\frac{2\pi k dj}{N} }(y_k-\frac{1}{2} x_k )e^{j\frac{\pi}{N}k}=\frac{1}{2N}(\sum^{N-1}_{k=0}e^{\frac{2\pi k dj}{N} }\sum^{N-1}_{p=0}\hat y_{2p+1}e^{-j\frac{\pi}{N}(2pk)})$$ $y_k=x_k$ within current bound $$\sum^{N-1}_{k=0}e^{\frac{2\pi k dj}{N} }(\frac{1}{2} x_k )e^{j\frac{\pi}{N}k}=\frac{1}{2N}(\sum^{N-1}_{k=0}e^{\frac{2\pi k dj}{N} }\sum^{N-1}_{p=0}\hat y_{2p+1}e^{-j\frac{\pi}{N}(2pk)})$$ $$\sum^{N-1}_{k=0}e^{\frac{2\pi k dj}{N} }( x_k )e^{j\frac{\pi}{N}k}=\frac{1}{N}(\sum^{N-1}_{k=0} \sum^{N-1}_{p=0}\hat y_{2p+1}e^{-j\frac{2k\pi}{N}(p-d)})$$ $$\sum^{N-1}_{k=0}e^{\frac{2\pi k dj}{N} }( x_k )e^{j\frac{\pi}{N}k}=\frac{1}{N}(\sum^{N-1}_{p=0} \hat y_{2p+1}\sum^{N-1}_{k=0}e^{-j\frac{2k\pi}{N}(p-d)})$$ By Gauss's identity, $d=p$ is the only time this isn't $0$ so giving the leftest value of the sum $N$ and the other as $\hat y_{2d+1}$. So we have $$\hat y_{2d+1}=\sum^{N-1}_{k=0}e^{\frac{2\pi k dj}{N} }( x_k )e^{j\frac{\pi}{N}k}$$ $$=\sum^{N-1}_{k=0}( x_k )e^{j\frac{(2d+1)}{N}\pi k}$$ using the inverse of the Discrete Fourier Transform's kth vector entry, we get $$=\sum^{N-1}_{k=0}( \frac{1}{N} \sum^{N-1}_{m=0} \hat x_me^{-j\frac{2m}{N}\pi k} )e^{j\frac{(2d+1)}{N}\pi k}$$ $$=\frac{1}{N} \sum^{N-1}_{m=0} \hat x_m \sum^{N-1}_{k=0}e^{j\frac{(2d+1)-2m}{N}\pi k}$$ with the Geometric Series formula, we get $$=\frac{1}{N} \sum^{N-1}_{m=0} \hat x_m \bigg(\frac{1-e^{j((2d+1)-2m)\pi}}{1-e^{j\frac{(2d+1)-2m}{N}\pi}}\bigg)$$ $$=\frac{1}{N} \sum^{N-1}_{m=0} \hat x_m \bigg(\frac{1-e^{j((2d+1)-2m)\pi}}{1-e^{-j\frac{-(2d+1)+2m}{N}\pi}}\bigg)$$ via Euler's identity, we have a period of $\pi$ always, which means $e^{j((2d+1)-2m)\pi}=-1$. So
$$=\frac{1}{N} \sum^{N-1}_{m=0} \hat x_m \bigg(\frac{1-(-1)}{1-e^{-j\frac{-(2d+1)+2m}{N}\pi}}\bigg)=\frac{1}{N} \sum^{N-1}_{m=0} \hat x_m \bigg(\frac{2}{1-e^{-j\frac{2m-(2d+1)}{N}\pi}}\bigg)$$ so we have our solution $$\hat y_{2d+1} =\frac{2}{N} \sum^{N-1}_{m=0} \hat x_m \bigg(\frac{1}{1-e^{-j\frac{2m-(2d+1)}{N}\pi}}\bigg)$$