Math Is Fun Forum

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Double Summation

Sorry about all the working... would someone mind telling me what I've done wrong / should have done (hints rather than full solutions please)

Thanks!

Last edited by Daniel123 (2008-11-02 11:00:08)

TheDude

Member

Registered: 2007-10-23

Posts: 361

Re: Double Summation

First, you'll need to break this down into cases where n is even and when it's odd.  You could use the floor function, but I'm not comfortable with it and prefer just to do the work twice.  If you're ok with it then go ahead.

Your work assumes an even n, so let's go with that.  Your 3rd to last line is the same thing I got, so it appears to be correct.  Going from that to the next line you skipped several steps of work, and this is where the error is.  Try substituting n=6 in those two lines.  On the 3rd to last line you get 6 + 2[4 + 2 + 0] = 6 + 2[6] = 18.  Using n=6 on the 2nd to last line you get 6 + 2[ { (6 - 2) + 2} * { (6 - 2) / 2} ] = 6 + 2[6 * 2] = 30.

My only advice here is to be deliberate when you use something like summation, especially when you're dealing with non-trivial values.  Here is how I would follow your 3rd to last line:

You should be able to work it from here, just be careful when you separate out pieces of the summation.

If you want to compare final answers I get

when n is even and

when n is odd.

---

Wrap it in bacon

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Double Summation

Brilliant, thanks. I'm glad it was an algebra slip rather than a conceptual one (I was typing my working straight into LaTeX.. maybe I should use paper next time )

Thanks again

Last edited by Daniel123 (2008-10-30 04:49:28)

TheDude

Member

Registered: 2007-10-23

Posts: 361

Re: Double Summation

Well, don't be too happy just yet, I'm not convinced that I'm right either .  I was just checking your algebra.  For one thing I think you need to prove your assumption that the greatest sum is achieved when xi alternates between 1 and 0, unless this is from some theorem that I'm unaware of.

---

Wrap it in bacon

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Double Summation

Actually, when you worked it through for odd n, did you use x_1 = 1 or x_1 = 0?

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Double Summation

Well, don't be too happy just yet, I'm not convinced that I'm right either .  I was just checking your algebra.  For one thing I think you need to prove your assumption that the greatest sum is achieved when xi alternates between 1 and 0, unless this is from some theorem that I'm unaware of.

Well I just tried it for n = 4 and n = 6 and it worked, so I'm going to assume it's right.

And yeah, I've still got to prove that. I can 'see' it, but I haven't tried explaining it. I'll let you know what I come up with (or don't come up with as the case may be).

TheDude

Member

Registered: 2007-10-23

Posts: 361

Re: Double Summation

I used x_1 = 1 for both even and odd values of n.

---

Wrap it in bacon

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Double Summation

Hmm.. I'm finding it difficult to explain why the sum is maximised when the values alternate between 0 and 1.

Can anyone help?

Thanks.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Double Summation

Remember that if term by term, a_n  <= b_n for all n, then the sum of all a_n <= the sum of all b_n.  Now simply prove that for a single general term, a_n <= b_n.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Double Summation

I don't follow.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Double Summation

It would help to know what it is you don't follow.  I will assume you're ok with the theorem that if a_n <= b_n for all n, then sum a_n <= sum b_n.

So what you want to show is that for all a and b in [0, 1], that |a - b| <= |1 - 0| = 1.  Once you have this, you have that for any sum that contains a term (or more!) that is not of the form |1 - 0| or |0 - 1| that a_n <= b_n (where b_n is your series of terms |1 - 0| or |0 - 1|) for all n, and so we conclude sum a_n <= sum b_n, as required.

Here, I'm using a_n as representing |x_i - x_j| whilst b_n represents terms of the form |0 - 1| or |1 - 0|.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Double Summation

Thanks, you've explained that well.

The reason I didn't think it required proof in the first place is because it's so obvious that |a-b| <= |1-0| for all a and b in [0, 1]; it's because of this that I decided that the terms should alternate between 0 and 1.

Last edited by Daniel123 (2008-11-02 07:01:24)

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Double Summation

Hmm... but not every term in my sum is |1-0| or |0-1|. Some are |0-0| or |1-1|. How do I account for that?

TheDude

Member

Registered: 2007-10-23

Posts: 361

Re: Double Summation

Instead of going term-by-term, use pairs.  Show that |a - b| + |b - c| <= |1 - 0| + |1 - 1| = 1 for all 0 <= a, b, c <= 1.

---

Wrap it in bacon

Kurre

Member

Registered: 2006-07-18

Posts: 280

Re: Double Summation

I havent fully read your solution, but a hint for another solution would be to assume WLOG that

to get rid of the absolute values, then count how many x_j there are for each j. After that its kind of straight forward.

(I get the same result as you btw, ~half will be 0, ~half will be 1 to get maximum)