- #1
aka mor
- 1
- 0
Hello everyone,
This seems like a simple problem but I get the impression that I'm missing something.
1. Homework Statement
Given the values ## v_1,v_2,...,v_n ## such that DFTn ## (P(x)) = (v_1, v_2, \ldots, v_n) ## and ##deg(P(x)) < n##, find DFT2n## P(x^2)##
My attempt:
Let [itex]P(x) = \sum\limits_{i=0}^{k} a_ix^i[/itex] .
First, expand ##P(x^2)## :
[tex]P(x^2) = a_0 + a_1x^2 + a_2x^4 + \ldots + a_kx^{2k}[/tex]
Let's denote by ##W^j_n## the j'th root of unity of order n.
We have:
[tex]W^j_{2n} = e^{\frac{2\pi i j}{2n}} = e^{\frac{\pi i j}{n }}[/tex]
Using this information, let's expand a term p of ##P(x^2)## on ##W^j_{2n}##:
[tex]a_p(x^2) = a_p(e^\frac{\pi ij}{n})^{2p} = a_p(e^{2\pi i}) ^\frac{jp}{n} = a_p[/tex] (since ##e^{2\pi i} = 1## ).
So, when evaluating any term of the compound polynomial on some unity root of order 2n we get ##\sum\limits_{i=0} ^k ak## and therefore the final answer is:
[tex](\sum\limits_{i=0} ^k ak, \sum\limits_{i=0} ^k ak,\ldots, \sum\limits_{i=0} ^k ak)[/tex].
This doesn't seem right, I didn't even use the information about ## (v_1, \ldots, v_n) ## (answer should be in terms of those?).
Any help would be appreciated.
This seems like a simple problem but I get the impression that I'm missing something.
1. Homework Statement
Given the values ## v_1,v_2,...,v_n ## such that DFTn ## (P(x)) = (v_1, v_2, \ldots, v_n) ## and ##deg(P(x)) < n##, find DFT2n## P(x^2)##
Homework Equations
The Attempt at a Solution
My attempt:
Let [itex]P(x) = \sum\limits_{i=0}^{k} a_ix^i[/itex] .
First, expand ##P(x^2)## :
[tex]P(x^2) = a_0 + a_1x^2 + a_2x^4 + \ldots + a_kx^{2k}[/tex]
Let's denote by ##W^j_n## the j'th root of unity of order n.
We have:
[tex]W^j_{2n} = e^{\frac{2\pi i j}{2n}} = e^{\frac{\pi i j}{n }}[/tex]
Using this information, let's expand a term p of ##P(x^2)## on ##W^j_{2n}##:
[tex]a_p(x^2) = a_p(e^\frac{\pi ij}{n})^{2p} = a_p(e^{2\pi i}) ^\frac{jp}{n} = a_p[/tex] (since ##e^{2\pi i} = 1## ).
So, when evaluating any term of the compound polynomial on some unity root of order 2n we get ##\sum\limits_{i=0} ^k ak## and therefore the final answer is:
[tex](\sum\limits_{i=0} ^k ak, \sum\limits_{i=0} ^k ak,\ldots, \sum\limits_{i=0} ^k ak)[/tex].
This doesn't seem right, I didn't even use the information about ## (v_1, \ldots, v_n) ## (answer should be in terms of those?).
Any help would be appreciated.
Last edited by a moderator: