Root of Unity Filters (RUF) Theorem
by huynguyen, Aug 7, 2015, 3:45 PM
Problem C2:
Let
be the generating function of the sequence {
}.
Let
be a complex number satisfying that 
.Prove that:
![$a_0+a_n+a_{2n}+a_{3n}+...=\frac{1}{n}.[P(1)+P(z)+...+P(z^{n-1})]$](//latex.artofproblemsolving.com/d/e/e/dee324d5e2e6b48667dc1dbac50b58821ec36f41.png)
Solution:
First, we will prove the following lemma:
Lemma:
(
) makes a residue system mod 
(
are coprime). (*)
Proof:
Contradicting the statement, assume
and 
are belongs to the above set and 
are congruent mod .
is divisible by , which is a contradiction since 
, ()
.
So (*) has been proved.
Back to the problem:
We get:
But by (*), we get:
for all 
coprime with .
Hence:
![$\Rightarrow a_0+a_n+a_{2n}+a_{3n}+...=\frac{1}{n}.[P(1)+P(z)+...+P(z^{n-1})]$](//latex.artofproblemsolving.com/2/4/d/24d19b0cd48fbe228070ddc362d5e4fa7506c1e6.png)
Q.E.D
Let
be the generating function of the sequence {
}.Let
be a complex number satisfying that 
.Prove that:![$a_0+a_n+a_{2n}+a_{3n}+...=\frac{1}{n}.[P(1)+P(z)+...+P(z^{n-1})]$](http://latex.artofproblemsolving.com/d/e/e/dee324d5e2e6b48667dc1dbac50b58821ec36f41.png)
Solution:
First, we will prove the following lemma:
Lemma:
(
) makes a residue system mod 
(
are coprime). (*)Proof:
Contradicting the statement, assume
and 
are belongs to the above set and 
are congruent mod .
is divisible by , which is a contradiction since 
, ()
.So (*) has been proved.
Back to the problem:
We get:
But by (*), we get:
for all 
coprime with .Hence:
![$\Rightarrow a_0+a_n+a_{2n}+a_{3n}+...=\frac{1}{n}.[P(1)+P(z)+...+P(z^{n-1})]$](http://latex.artofproblemsolving.com/2/4/d/24d19b0cd48fbe228070ddc362d5e4fa7506c1e6.png)
Q.E.D
This post has been edited 2 times. Last edited by huynguyen, Aug 7, 2015, 4:44 PM
July 2016
June 2016