Challenge Problem

[jinydu]

Originally Posted by Zeta-Flux

That looks exactly right. The formula is not hard to prove actually. All you have to do is look at S(m-k)Pi(k), and figure out exactly what the monomials look like. They break up into two kinds. The monomials where the higest power on any variable is k and all the other variable have order 1, and monomials where the higest power on any variable is k+1 and the other variables have order 1. Then, grouping in this way, the sum just telescopes to zero.


For example, take n=3, so we have A(1), A(2), A(3). Let m=3, k=1. So we are looking at S(m-k)Pi(k)=S(2)Pi(1)=(A_1 A_2 +A_1 A_3 + A_2 A_3)(A_1 +A_2 + A_3) = [ A_1^2 A_2 +A_1^2 A_3 + A_2^2 A_1 +A_2^2 A_3 +A_3^2 A_1 +A_3^2 A_2] + 3[A_1 A_2 A_3]. Notice in the first group that the highest power is just 2, and in the second group the highest power is 1. Do the same type of grouping on S(1)Pi(2), Pi(3), and S(3), and the different groups just cancel each other out, and the proof follows.
--------

By the way, an alternate question to ask is will this same method work if we use a field that is different than the complex numbers. (Say, a finite field.)

I've actually had another look at this, and I've almost managed to prove the Newton-Girard Formulas:

Anyway, here's a "proof" of the Newton-Girard Formulas that contains that one gap.

Let r(1), r(2), r(3) ... r(n) and c(0), c(1), c(2) ... c(n-1) be arbitrary complex numbers.

Define

P(1) = r(1) + r(2) + r(3) + ... + r(n)
P(2) = Sum of all r's taken 2 at a time
P(3) = Sum of all r's taken 3 at a time
...
P(n) = r(1) * r(2) * r(3) * ... * r(n)

S(1) = r(1) + r(2) + r(3) + ... + r(n)
S(2) = r(1)^2 + r(2)^2 + r(3)^2 + ... + r(n)^2
S(3) = r(1)^3 + r(2)^3 + r(3)^3 + ... + r(n)^3
...
S(n) = r(1)^n + r(2)^n + r(3)^n + ... + r(n)^n

Now, assume that:

P(1) = -c(n-1)
P(2) = c(n-2)
P(3) = -c(n-3)
...
P(n-1) = (-1)^(n-1) * c(1)
P(n) = (-1)^n * c(0)

Finally, define the polynomial p(x):

x^n + c(n-1)*x^(n-1) + c(n-2)*x^(n-2) + ... + c(1)*x + c(0) = 0

Suppose that I could prove that r(1), r(2), r(3) ... r(n) are the roots of p(x) (this is just the converse of Vieta's Formulas). Then by definition of root:

r(1)^n + c(n-1)*r(1)^(n-1) + c(n-2)*r(1)^(n-2) + ... + c(1)*r(1) + c(0) = 0

r(2)^n + c(n-1)*r(2)^(n-1) + c(n-2)*r(2)^(n-2) + ... + c(1)*r(2) + c(0) = 0

r(3)^n + c(n-1)*r(3)^(n-1) + c(n-2)*r(3)^(n-2) + ... + c(1)*r(3) + c(0) = 0

...

r(n)^n + c(n-1)*r(n)^(n-1) + c(n-2)*r(n)^(n-2) + ... + c(1)*r(n) + c(0) = 0

We're going to have to add all those equations together, term by term. To do this, it is convenient to use the S(n) notation. After adding together all the equations, we get just one equation:

S(n) + c(n-1)*S(n-1) + c(n-2)*S(n-2) + ... + c(1)*S(1) + n*c(0)

Applying the assumption that:

P(1) = -c(n-1)
P(2) = c(n-2)
P(3) = -c(n-3)
...
P(n-1) = (-1)^(n-1) * c(1)
P(n) = (-1)^n * c(0)

We have:

S(n) - S(n-1)*P(1) + S(n-2)*P(2) + ... + S(1)*(P(n-1)/(-1)^(n-1)) + n*(P(n)/((-1)^n)) = 0

But 1/((-1)^(n-1)) = 1 or -1

If 1/((-1)^(n-1)) = 1,
then (-1)^(n-1) = 1 = 1/((-1)^(n-1))

If 1/((-1)^(n-1)) = -1
then (-1)^(n-1) = -1 = 1/((-1)^(n-1))

Also,

1/((-1)^n) = 1/(-1 * (-1)^(n-1))

= -1 * 1/((-1)^(n-1))

= -1 * (-1)^(n-1)

= (-1)^n

Thus, we can simplify that equation:

S(n) - S(n-1)*P(1) + S(n-2)*P(2) + ... + S(1)*(P(n-1)/(-1)^(n-1)) + n*(P(n)/((-1)^n)) = 0

by substituting

P(n-1)/((-1)^(n-1)) = P(n)*(-1)^(n-1)

P(n)/((-1)^n) = P(n)*(-1)^n

Thus, we have

S(n) - S(n-1)*P(1) + S(n-2)*P(2) + ... + S(1)*P(n-1)*(-1)^(n-1) + n*P(n)*(-1)^n = 0

This is precisely the Newton-Girard Formula

Q.E.D.

(Except I don't know how to prove the converse of Vieta's Formulas)

[Zeta-Flux]

jinydu,

You want to prove r_1, r_2, ..., r_n are each roots of f(x)=x^{n} - P(1) x^{n-1} + P(2) x^{n-2} ... + (-1)^{n} P(n). First, notice that it suffices to show that r_1 is a root, since the coefficients of f(x) are symmetric. Why? Let g be the map that switches r_1 with r_i, and leaves all the other r's alone. Then g(f(x))=f(g(x)) since the coefficients of f(x) are symmetric! (That's the beauty of symmetric polynomials.) Therefore 0=g(0)=g(f(r_1))=f(g(r_1))=f(r_i). So if r_1 is a root, so are all the other r's.

Now, why is r_1 a root?? Check a few examples, like n=1, n=2, n=3. You should start seeing a pattern.

Best,
Zeta-Flux

[jinydu]

Hmmm, why didn't I see this before?

Suppose that

P(1) = -c(n-1)
P(2) = c(n-2)
P(3) = -c(n-3)
...
P(n-1) = (-1)^n-1 * c(1) = c(1)/((-1)^(n-1))
P(n) = (-1)^n * c(0) = c(0)/((-1)^n)

Define the polynomial

p(x) = x^n + c(n-1)*x^(n-1) + c(n-2)*x^(n-2) + ... + c(1)*x + c(0)

Using the previous equations to eliminate the coefficients:

p(x) = x^n - P(1)*x^(n-1) + P(2)*x^(n-2) - ... + ((-1)^(n-1))*P(n-1)*x + ((-1)^n)*P(n)

By Vieta's Formulas, we can factor this:

p(x) = (x - r(1))*(x - r(2))*(x - r(3))*...*(x - r(n))

Therefore, r(1), r(2), r(3) ... r(n) are roots of the equation.

Q.E.D.

Basically, the main point is that factorization and expansion work both ways. That's what I overlooked before...

Unfortunately, I've taken a closer look at the Newton-Girard Formulas, and found that my proof only proves a special case of the Newton-Girard Formulas.

I've only proven that the formula is valid when the number of variables equals the maximum degree of the power sums. However, Mathworld claims that the formula is valid for any number of variables, independent of the maximum degree of the power sums. And in fact, I need the general formula in order to use your method...

Here's an example:

My theorem asserts that:

(A^2 + B^2) - (A + B)*(A + B) + 2AB = 0

The 2nd Newton-Girard Formula asserts that:

(A(1)^2 + A(2)^2 + ... + A(n)^2) - (A(1) + A(2) + ... + A(n))*(A(1) + A(2) + ... + A(n)) + 2(A(1)*A(2) + A(1)*A(3) + ... + A(n-1)*A(n)) = 0

Nevertheles, this special case that I've proved is still good enough to prove that if:

A(1) + A(2) + A(3) + ... + A(n) = 0
A(1)^2 + A(2)^2 + A(3)^2 + ... + A(n)^2 = 0
A(1)^3 + A(2)^3 + A(3)^3 + ... + A(n)^3 = 0
...
A(1)^n + A(2)^n + A(3)^n + ... + A(n)^n = 0

Then the only solution is A(1) = A(2) = A(3) = ... = A(n) = 0

I am able to do this because I only need the nth Newton-Girard Formula, and only for n variables.

Here's how the proof goes. Its really a quick proof by induction.

For the case when n = 1, we have just A(1) = 0. Obviously, the only solution is that A(1) = 0.

Assume that the assertion is true for n. That is, if:

A(1) + A(2) + A(3) + ... + A(n) = 0
A(1)^2 + A(2)^2 + A(3)^2 + ... + A(n)^2 = 0
A(1)^3 + A(2)^3 + A(3)^3 + ... + A(n)^3 = 0
...
A(1)^n + A(2)^n + A(3)^n + ... + A(n)^n = 0

Then the only solution is A(1) = A(2) = A(3) = ... = A(n) = 0. Keep that in mind, as we'll use it later.

Now, consider what happens for the n + 1 case. We have the system of equations:

A(1) + A(2) + A(3) + ... + A(n) + A(n+1) = 0
A(1)^2 + A(2)^2 + A(3)^2 + ... + A(n)^2 + A(n+1)^2 = 0
A(1)^3 + A(2)^3 + A(3)^3 + ... + A(n)^3 + A(n+1)^3 = 0
...
A(1)^n + A(2)^n + A(3)^n + ... + A(n)^n + A(n+1)^n = 0
A(1)^(n+1) + A(2)^(n+1) + A(3)^(n+1) + ... + A(n)^(n+1) + A(n+1)^(n+1) = 0

Apply my special case of the Newton-Girard Formulas to conclude that

S(n+1) - S(n)*P(1) + S(n-1)*P(2) + ... + S(1)*P(n)*(-1)^(n) + (n+1)*P(n+1)*(-1)^(n+1) = 0

By the given conditions, we have

S(1) = 0
S(2) = 0
S(3) = 0
...
S(n) = 0
S(n+1) = 0

Thus, all the terms are equal to zero except the last one, and we have:

(n+1)*P(n+1)*(-1)^(n+1) = 0

Clearly, (n+1) can't be 0, since n is a positive integer, and (-1)^(n+1) can't be zero either, since it can only be -1 or 1. So the only possibility is that:

P(n+1) = 0

Since we have n+1 variables, this means that

A(1)*A(2)*A(3)*...*A(n)*A(n+1) = 0

Thus, it follows that at least one of variables are zero. Now ignore the last equation:

A(1)^(n+1) + A(2)^(n+1) + A(3)^(n+1) + ... + A(n)^(n+1) + A(n+1)^(n+1) = 0

And arbitrarily set one of the variables equal to zero, allowing us to delete a column in our remaining system of equations.

We're now left with a system of n variables up to the nth powers, which is exactly case n. All the variables in this system of equations must equal 0, by the induction assumption. Thus, the assumption that all the variables equal 0 in case n implies the assertion for case n+1, so the proof by induction is complete.

Q.E.D.

Considering this was my initial problem, that's quite comforting, although I would like the general proof.

[jinydu]

Originally Posted by jinydu

I've only proven that the formula is valid when the number of variables equals the maximum degree of the power sums. However, Mathworld claims that the formula is valid for any number of variables, independent of the maximum degree of the power sums. And in fact, I need the general formula in order to use your method...

Whoops, that was a mistake. I'll admit, I copied this from a message I posted somewhere else.

But I still don't how to prove the Newton-Girard formulas for any number of variables. I can do it for the first [S(1) - P(1) = 0] and second
[S(2) - S(1)*P(1) + 2P(2) = 0] formulas, but I haven't been able to do it in general.

I'll admit that part of the reason is that one of my university courses has been giving me a lot of trouble.

[jinydu]

The first formula is trivial, since it just states that

(A(1) + A(2) + A(3) + ... + A(n)) - (A(1) + A(2) + A(3) + ... + A(n)) = 0

The second formula can be done using a proof by induction. Using the S and P notation:

S(2) - S(1)*P(1) + 2P(2) = 0

Since we already know that S(1) = P(1), that becomes

S(2) - S(1)^2 + 2P(2) = 0

Suppose we have just one variable, A. Then:

S(2) = A^2
S(1) = A
P(2) = 0

So, the Newton-Girard formula just says

A^2 - A^2 = 0, which is obviously true.

Now, assume it is true for n variables:

(A(1)^2 + A(2)^2 + ... + A(n)^2) - (A(1) + A(2) + ... + A(n))^2 + 2(A(1)*A(2) + A(1)*A(3) + ... + A(n-1)*A(n)) = 0

To transform the first parenthesis into the form for (n+1) variables, we just add (A(n+1))^2 to both sides. So we have (A(n+1))^2 on the right-hand side.

To transfrom the second parenthesis into the (n+1) form, remember that

S(1) = A(1) + A(2) + ... + A(n)

Essentially, we want is

(S(1) + A(n+1))^2

Subtracting this from S(1)^2 gives

2S(1)*A(n+1) + (A(n+1))^2

In fact, we have to subtract this from both sides, because the second term is negative. Thus, on the right hand side, we have

(A(n+1))^2 - (2S(1)*A(n+1) + (A(n+1))^2)

= -2S(1)*A(n+1)

Finally, we adjust the third term on the left hand side.

Essentially, we have to consider all the new two-at-a-time combinations resulting from adding a new term. Each of these combinations must contain A(n+1) as a factor, while the other factor can be any of the original n terms. Thus, we have to add to both sides

2(A(n+1)*A(1) + A(n+1)*A(2) + A(n+1)*A(3) + ... + A(n+1)*A(n))

We can factor A(n+1) out of that:

2A(n+1)*(A(1) + A(2) + A(3) + ... + A(n))

And since A(1) + A(2) + ... + A(n) = S(1), that's just equal to:

2A(n+1)*S(1)

Finally, if we add that to both sides, the left-hand side becomes exactly the form for (n+1) variables. When we add it to the right-hand side, we get:

-2S(1)*A(n+1) + 2A(n+1)*S(1) = 0

Thus, the truth of the formula for n variables implies the truth of the formula for (n+1) variables. Together with the result that the formula is good for 1 variable, this completes the proof by induction.

Therefore, the 2nd Newton-Girard formula is valid for any number of variables.

Q.E.D.

Even though I haven't done the 3rd formula (let alone the general formula), I have an interesting application for the 2nd formula.

Since the formula, S(2) - S(1)*P(1) + 2P(2) = 0, is valid for any finite number of variables, why not assume that it will work for infinitely many variables? In that case, we would have:

S(2) = A(1)^2 + A(2)^2 + A(3)^2 + ...

S(1) = A(1) + A(2) + A(3) + A(4) + ... = P(1)

P(2) = A(1)*A(2) + A(1)*A(3) + A(2)*A(3) + ...

In Euler's proof that 1 + 1/4 + 1/9 + 1/16 + 1/25 + ... = (pi^2)/6, he establishes the following equation:

(1 - (x^2)/(pi^2)) * (1 - (x^2)/(4pi^2)) * (1 - (x^2)/(9pi^2)) * ... = 1 - (x^2)/3! + (x^4)/5! - (x^6)/7! + ...

I already know that by equating the x^2 coefficients, one derives that 1 + 1/4 + 1/9 + 1/16 + 1/25 = (pi^2)/6. But what happens when we equate the x^4 coefficients?

Well, the x^4 coefficient on the right-hand side is easy. Its just 1/5!, or 1/120. What about the x^4 coefficient on the left-hand side?

Imagine "multiplying out" the infinite product on the left-hand side. The x^4 coefficient would then be just the (infinite) sum of all the x^4 terms. What are these terms? Well, one term is formed by multiplying -(x^2)/(pi^2) by -(x^2)(4pi^2). Another term is formed by -(x^2)/(pi^2) * -(x^2)/(9pi^2). In general, a term is formed everytime we multiply two -(x^2)/(n^2 * pi^2)'s together.

Notice how this fits in perfectly with our P notation. The total x^4 coefficient on the left-hand side is just the sum of all the -(x^2)/(n^2 * pi^2)'s, taken two at a time. Therefore, the x^4 coefficient is just P(2), where

A(1) = -1/(pi^2)
A(2) = -1/(4pi^2)
A(3) = -1/(9pi^2)
...
A(n) = -1/(n^2 * pi^2)
...

Equating the x^4 coefficients on both sides, we get:

P(2) = 1/120

Also, what is the value of S(1)? By definition, it is just:

A(1) + A(2) + A(3) + ...

= -1/(pi^2) - 1/(4pi^2) - 1/(9pi^2) - ...

Using either the preexisting result that 1 + 1/4 + 1/9 + 1/16 + 1/25 + ... = (pi^2)/6, or by equating the x^2 coefficients, we know that

S(1) = -1/6 = P(1)

Now, we can use the 2nd Newton-Girard Formula, S(2) - S(1)*P(1) + 2P(2) = 0, to solve for S(2)

S(2) - (-1/6)*(-1/6) + 2(1/120) = 0

S(2) - 1/36 + 1/60 = 0

S(2) = 1/36 - 1/60

S(2) = 1/90

But what is S(2)? By definition, it is:

S(2) = (-1/(pi^2))^2 + (-1/(4pi^2))^2 + (-1/(9pi^2))^2 + ... + (-1/(n^2 * pi^2))^2 + ...

S(2) = 1/(pi^4) + 1/(16pi^4) + 1/(81pi^4) + ... + (1/n^4 * pi^4) + ...

Thus,

1/(pi^4) + 1/(16pi^4) + 1/(81pi^4) + ... + (1/n^4 * pi^4) + ... = 1/90

Multiplying both sides by pi^4:

1 + 1/16 + 1/81 + 1/256 + 1/625 + 1/1296 + ... + 1/(n^4) + ... = (pi^4)/90

[jinydu]

I've been given a link to a proof of the Newton-Girard Formulas. At first sight it looks short and reasonably elementary. But its quite dense, and does seem to rely on a few theorems that I don't know:

http://www.math.ubc.ca/~reichst/nf.ps