Help me prove/disprove this trig conjecture

OK.  This is probably stupid.

For n even, the sum from k = 1 to k = n of cos(2 * pi * k/n + phi) is 
zero, almost by inspection.  (Divide k up into the 1 to 1/n part and the 
other part -- every cos(etc) in the first part has a cos(etc + pi) in the 
second part.  Cancel, done).

I'm almost certain that this is true for n odd.

Anyone know for sure?  Have a reference and/or easy proof?  Or do I need 
to do a bunch of trig?

Thanks.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

On Wed, 29 Apr 2015 17:10:02 -0500, Tim Wescott wrote:

> OK.  This is probably stupid.
> 
> For n even, the sum from k = 1 to k = n of cos(2 * pi * k/n + phi) is
> zero, almost by inspection.  (Divide k up into the 1 to 1/n part and the
> other part -- every cos(etc) in the first part has a cos(etc + pi) in
> the second part.  Cancel, done).
> 
> I'm almost certain that this is true for n odd.
> 
> Anyone know for sure?  Have a reference and/or easy proof?  Or do I need
> to do a bunch of trig?
> 
> Thanks.

Argh.  I have an easy, obvious, graphical demonstration that still isn't a 
proof!!

Take a massless circular disk, and distribute n identical ball bearings 
evenly around it's periphery.  It's center of gravity is in the center of 
the disk.  This can be worked into the above trig proof.  But I still 
don't have a mathemagical proof, dammit!

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

On 2015-04-29 23:07:51 +0000, Tim Wescott said:

> On Wed, 29 Apr 2015 17:10:02 -0500, Tim Wescott wrote:
> 
>> OK.  This is probably stupid.
>> 
>> For n even, the sum from k = 1 to k = n of cos(2 * pi * k/n + phi) is
>> zero, almost by inspection.  (Divide k up into the 1 to 1/n part and the
>> other part -- every cos(etc) in the first part has a cos(etc + pi) in
>> the second part.  Cancel, done).
>> 
>> I'm almost certain that this is true for n odd.
>> 
>> Anyone know for sure?  Have a reference and/or easy proof?  Or do I need
>> to do a bunch of trig?
>> 
>> Thanks.
> 
> Argh.  I have an easy, obvious, graphical demonstration that still isn't a
> proof!!
> 
> Take a massless circular disk, and distribute n identical ball bearings
> evenly around it's periphery.  It's center of gravity is in the center of
> the disk.  This can be worked into the above trig proof.  But I still
> don't have a mathemagical proof, dammit!

The oldest recipe in math proofs is to reduce it to a previous problem.
Here that means getting rid of the phi issue. Use the cos of two angles
to get a more complicted appearing form that allows the sin(phi)and cos(phi)
terms to be factored out which leaves two old problems. One in sin and the
other in cos. Details left as an exercise for the reader.

On Wed, 29 Apr 2015 20:20:25 -0300, Gordon Sande wrote:

> On 2015-04-29 23:07:51 +0000, Tim Wescott said:
> 
>> On Wed, 29 Apr 2015 17:10:02 -0500, Tim Wescott wrote:
>> 
>>> OK.  This is probably stupid.
>>> 
>>> For n even, the sum from k = 1 to k = n of cos(2 * pi * k/n + phi) is
>>> zero, almost by inspection.  (Divide k up into the 1 to 1/n part and
>>> the other part -- every cos(etc) in the first part has a cos(etc + pi)
>>> in the second part.  Cancel, done).
>>> 
>>> I'm almost certain that this is true for n odd.
>>> 
>>> Anyone know for sure?  Have a reference and/or easy proof?  Or do I
>>> need to do a bunch of trig?
>>> 
>>> Thanks.
>> 
>> Argh.  I have an easy, obvious, graphical demonstration that still
>> isn't a proof!!
>> 
>> Take a massless circular disk, and distribute n identical ball bearings
>> evenly around it's periphery.  It's center of gravity is in the center
>> of the disk.  This can be worked into the above trig proof.  But I
>> still don't have a mathemagical proof, dammit!
> 
> The oldest recipe in math proofs is to reduce it to a previous problem.
> Here that means getting rid of the phi issue. Use the cos of two angles
> to get a more complicted appearing form that allows the sin(phi)and
> cos(phi)
> terms to be factored out which leaves two old problems. One in sin and
> the other in cos. Details left as an exercise for the reader.

Well, is there an easy-to-find proof for phi=0 then?

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

On 30.04.2015 1:10, Tim Wescott wrote:
> OK.  This is probably stupid.
>
> For n even, the sum from k = 1 to k = n of cos(2 * pi * k/n + phi) is
> zero, almost by inspection.  (Divide k up into the 1 to 1/n part and the
> other part -- every cos(etc) in the first part has a cos(etc + pi) in the
> second part.  Cancel, done).
>
> I'm almost certain that this is true for n odd.
>
> Anyone know for sure?  Have a reference and/or easy proof?  Or do I need
> to do a bunch of trig?
>
> Thanks.
>

Tim, here you go.

Your sum is nothing else but the real part of the sum from k = 1 to k =
n of exp [j * (2 * pi * k/n + phi) ]. Since phi is common for all
numbers to sum up, your sum equals the real part of exp [j*phi]
multiplied by the sum from k = 1 to k = n of exp (j * 2 * pi * k/n).

Now, the sum from k = 1 to k = n of exp (j * 2 * pi * k/n) is the sum of
a geometrical proportion which equals [exp(j * 2 * pi * (n + 1)/n ) -
exp(j * 2 * pi / n)] / [exp(j * 2 * pi / n) - 1] which equals zero
(unless n = 1).

Finally, your sum, which is shown to be the real part of exp [j*phi] * 0
-- is zero, of course.

HTH.

Evgeny.

On 2015-04-29 23:27:19 +0000, Tim Wescott said:

> On Wed, 29 Apr 2015 20:20:25 -0300, Gordon Sande wrote:
> 
>> On 2015-04-29 23:07:51 +0000, Tim Wescott said:
>> 
>>> On Wed, 29 Apr 2015 17:10:02 -0500, Tim Wescott wrote:
>>> 
>>>> OK.  This is probably stupid.
>>>> 
>>>> For n even, the sum from k = 1 to k = n of cos(2 * pi * k/n + phi) is
>>>> zero, almost by inspection.  (Divide k up into the 1 to 1/n part and
>>>> the other part -- every cos(etc) in the first part has a cos(etc + pi)
>>>> in the second part.  Cancel, done).
>>>> 
>>>> I'm almost certain that this is true for n odd.
>>>> 
>>>> Anyone know for sure?  Have a reference and/or easy proof?  Or do I
>>>> need to do a bunch of trig?
>>>> 
>>>> Thanks.
>>> 
>>> Argh.  I have an easy, obvious, graphical demonstration that still
>>> isn't a proof!!
>>> 
>>> Take a massless circular disk, and distribute n identical ball bearings
>>> evenly around it's periphery.  It's center of gravity is in the center
>>> of the disk.  This can be worked into the above trig proof.  But I
>>> still don't have a mathemagical proof, dammit!
>> 
>> The oldest recipe in math proofs is to reduce it to a previous problem.
>> Here that means getting rid of the phi issue. Use the cos of two angles
>> to get a more complicted appearing form that allows the sin(phi)and
>> cos(phi)
>> terms to be factored out which leaves two old problems. One in sin and
>> the other in cos. Details left as an exercise for the reader.
> 
> Well, is there an easy-to-find proof for phi=0 then?

Yes. See the orthogonality conditions underlying the DFT.

>OK.  This is probably stupid.
>
>For n even, the sum from k = 1 to k = n of cos(2 * pi * k/n + phi) is 
>zero, almost by inspection.  (Divide k up into the 1 to 1/n part and the
>
>other part -- every cos(etc) in the first part has a cos(etc + pi) in
>the 
>second part.  Cancel, done).
>
>I'm almost certain that this is true for n odd.
>
>Anyone know for sure?  Have a reference and/or easy proof?  Or do I need
>
>to do a bunch of trig?
>
>Thanks.
>
>-- 
>
>Tim Wescott
>Wescott Design Services
>http://www.wescottdesign.com

The mathematical proof is fairly easy.

First recognize your range can be shifted from (1 to n) to (0 to n-1).

Second replace the cosine function with the exponential version from
Euler's equation, i.e. cos(x) = (e^ix+e^-ix)/2.

Third, split the summation in two.

Fourth, factor out the e^(i*phi)'s from the summations.  The summations
will now be geometric series.

Fifth, apply the geometric series formula to both summations.  The
numerators will both be zero.

I do a very similar proof in my blog article titled "DFT Bin Value
Formulas for Pure Real Tones" at DspRelated (dot) com.

Ced
---------------------------------------
Posted through http://www.DSPRelated.com

On 30.04.2015 18:34, Cedron wrote:

(snip)

 >Fourth, factor out the e^(i*phi)'s from the summations.  The summations
 >will now be geometric series.
 >
 >Fifth, apply the geometric series formula to both summations.  The
 >numerators will both be zero.

It's actually unnecessary to factor out e^(i*phi). The geometric series 
formula still holds if you don't factor out e^(i*phi), and the numerator 
in the formula is still zero.

Evgeny.

>On 30.04.2015 18:34, Cedron wrote:
>
>(snip)
>
> >Fourth, factor out the e^(i*phi)'s from the summations.
(snip)
>
>It's actually unnecessary to factor out e^(i*phi). The geometric series
>
>formula still holds if you don't factor out e^(i*phi), and the numerator
>
>in the formula is still zero.
>
>Evgeny.

Hi Evgeny,

I disagree.  It is still a geometric series because the ratio of terms is
constant, but the formula does not apply straight up.  You need to break
out the constant factor.

x^(k+c) = x^c * x^k = a * x^k

In the general form:

sum[k=0 to N-1]( ax^k ) = a * (1-x^N) / (1-x)

The 'a' is still being factored out.  So, in context, the e^(i*phi) still
needs to be factored out, whether you leave it inside the summation or
take it outside.

Ced

P.S.  The OP's original summation is the DC bin calculation of a pure real
tone with a frequency of 1 cycle per frame and an amplitude of 1.  I
forgot to mention that in my previous post.


---------------------------------------
Posted through http://www.DSPRelated.com

On Wednesday, April 29, 2015 at 5:10:06 PM UTC-5, Tim Wescott wrote:
> OK.  This is probably stupid.
> 
> For n even, the sum from k = 1 to k = n of cos(2 * pi * k/n + phi) is 
> zero, almost by inspection.

Actually, not quite. See the punchline (and counter example) at the very end.

Humans have a way of proclaiming brilliant discoveries that were, in fact, still partly unmade! Instead of proclaiming exp(2 pi i) = 1, we will actually DEFINE 1^x = exp(2 pi i x).

Rewrite phi as 2 pi phi and define each integer n = 0, 1, 2, 3, ... as the set of its predecessors and use k = 0 instead of k = n in the sum. Then the sum is over k in n.

The sum_{k in n} cos(2 pi (k/n + phi))
 = 1/2 sum_{k in n} 1^{k/n + phi}
 + 1/2 sum_{k in n} 1^{-k/n - phi}.

But the sum_{k in n} c^k = (c^n - 1)/(c - 1).

Therefore the sum is
   1/2 (1^{1 + phi} - 1^{phi})/(1^{1/n} - 1)
 + 1/2 (1^{-1 - phi} - 1^{-phi})/(1^{-1/n} - 1).

But 1^{1 + phi} = 1^1 1^phi = 1^phi and 1^{-1 - phi} = 1^{-1} 1^{-phi} = 1^{-phi}. Therefore, the sum is 0 ... as long as n is larger than 1.

The sum is NOT 0 if n = 1.