Index Manipulation of Summation in Real Cosine Transform Fast Computation

Question

Consider $X_k = \sum_{n=0}^{N-1}x_{n}\cos\frac{(2n+1)k\pi}{2N}$ for $k=0,1,2,...,N-1$. Now we define $g_{n} = x_{n} + x_{N-1-n}$ and $h_{n} = \frac{x_{n}-x_{N-1-n}}{2\cos\frac{(2n+1)k\pi}{2N}}$ for $\{x_{n}\}_{n=0}^{N-1}$ and $\{g_{n}\}_{n=0}^{\frac{N}{2}-1}$, $\{h_{n}\}_{n=0}^{\frac{N}{2}-1}$. Next, we also define $G_{k} = \sum_{n=0}^{\frac{N}{2}-1}g_{n}\cos\frac{(2n+1)k\pi}{N}$ and $H_{k}= \sum_{n=0}^{\frac{N}{2}-1}h_{n}\cos\frac{(2n+1)k\pi}{N}$. Note that $X_{k}$ is in the context of being the real cosine transform of $x_{n}$.
Show that $G_{k}=X_{2k}$ and $H_{k}+H_{k+1}=X_{2k+1}$!

So, here is my attempt so far:
Observe that
$$X_{2k}= \sum_{n=0}^{N-1}x_{n}\cos\frac{(2n+1)k\pi}{N}$$ $$X_{2k}= \sum_{n=0}^{\frac{N}{2}-1}x_{n}\cos\frac{(2n+1)k\pi}{N}+ \sum_{n=\frac{N}{2}}^{N-1}x_{n}\cos\frac{(2n+1)k\pi}{N}$$ $$X_{2k}= \sum_{n=0}^{\frac{N}{2}-1}x_{n}\cos\frac{(2n+1)k\pi}{N}+ \sum_{i=0}^{\frac{N}{2}-1}x_{i+\frac{N}{2}}\cos\big(\frac{(2i+1)k\pi}{N} + \frac{k\pi}{2}\big) $$ and I do not know what to do from here on since the form does not match.
Then, I also have tried the second part but I find myself to not be able to do further as well.
Observe that $$H_{k}+H_{k+1}= \sum_{n=0}^{\frac{N}{2}-1}h_{n}\cos\frac{(2n+1)k\pi}{N} + \sum_{n=0}^{\frac{N}{2}-1}h_{n}\cos\frac{(2n+1)(k+1)\pi}{N} $$ $$H_{k}+H_{k+1}= \sum_{n=0}^{\frac{N}{2}-1}h_{n}\bigg[\cos\frac{(2n+1)k\pi}{N} + \cos\frac{(2n+1)(k+1)\pi}{N}\bigg]$$ $$H_{k}+H_{k+1}= \sum_{n=0}^{\frac{N}{2}-1}h_{n}2\cos\frac{(2n+1)(2k+1)\pi}{2N}\cos\frac{(2n+1)\pi}{2N}$$ $$H_{k}+H_{k+1}= \sum_{n=0}^{\frac{N}{2}-1}\frac{x_{n}-x_{N-1-n}}{2\cos\frac{(2n+1)k\pi}{2N}}2\cos\frac{(2n+1)(2k+1)\pi}{2N}\cos\frac{(2n+1)\pi}{2N}$$ $$H_{k}+H_{k+1}= \sum_{n=0}^{\frac{N}{2}-1}(x_{n}-x_{N-1-n})\cos\frac{(2n+1)(2k+1)\pi}{2N}$$ $$H_{k}+H_{k+1}= \sum_{n=0}^{\frac{N}{2}-1}x_{n}\cos\frac{(2n+1)(2k+1)\pi}{2N}-\sum_{n=0}^{\frac{N}{2}-1}x_{N-1-n}\cos\frac{(2n+1)(2k+1)\pi}{2N}$$ Again, I do not know what I have to do at this point since I cannot manipulate the index of the summation to get the result I want.
Any help is much appreciated! Thank you!

Answer 1

Here is the first part. We want to show equality $G_k=X_{2k}$ with \begin{align*} G_k&=\sum_{n=0}^{\frac{N}{2}-1}\left(x_n+x_{N-1+n}\right)\cos\frac{(2n+1)k\pi}{N}\\ X_{2k}&=\sum_{n=0}^{N-1}x_n\cos\frac{(2n+1)k\pi}{N} \end{align*}

We obtain \begin{align*} \color{blue}{G_k}&\color{blue}{=\sum_{n=0}^{\frac{N}{2}-1}\left(x_n+x_{N-1+n}\right)\cos\frac{(2n+1)k\pi}{N}}\\ &=\underbrace{\sum_{n=0}^{\frac{N}{2}-1}x_n\cos\frac{(2n+1)k\pi}{N}}_{=: A}+\sum_{n=0}^{\frac{N}{2}-1}x_{N-1+n}\cos\frac{(2n+1)k\pi}{N}\\ &=A+\sum_{n=0}^{\frac{N}{2}-1}x_{N-1+\left(\frac{N}{2}-1-n\right)}\cos\frac{\left(2\left(\frac{N}{2}-1-n\right)+1\right)k\pi}{N}\tag{1}\\ &=A+\sum_{n=0}^{\frac{N}{2}-1}x_{\frac{N}{2}+n}\cos\frac{\left(N-1-2n\right)k\pi}{N}\\ &=A+\sum_{n=\frac{N}{2}}^{N-1}x_{\frac{N}{2}-\left(n+\frac{N}{2}\right)}\frac{\cos\left(N-1-2\left(n-\frac{N}{2}\right)\right)k\pi}{N}\tag{2}\\ &=A+\sum_{n=\frac{N}{2}}^{N-1}x_n\frac{\cos\left(2N-1-2n\right)k\pi}{N}\\ &=\sum_{n=0}^{\frac{N}{2}-1}x_n\cos\frac{(2n+1)k\pi}{N}+\sum_{n=\frac{N}{2}}^{N-1}x_n\cos\frac{(2n+1)k\pi}{N}\tag{3}\\ &\color{blue}{=\sum_{n=0}^{N-1}x_n\cos\frac{(2n+1)k\pi}{N}=X_{2k}} \end{align*} and the claim follows.

Comment:

• In (1) we change the order of summation of the right-hand sum: $n\rightarrow \frac{N}{2}-1-n$.

• In (2) we shift the index to start with $n=\frac{N}{2}$.

• In (3) we use that $\cos$ is an even function and periodic with period $2\pi$.