Thread: A Product

The product (1+x+x^2+x^3+...)(1+x^3+x^6+x^9+...)(1+x^5+x^10+.. .)... is the generating function for the number of partitions of n into odd parts.

How can you replace some of the plus signs with minus signs so that the resulting product when expanded has coefficients which are all either +1, zero, or -1?

(There are many solutions.)

Originally Posted by Partition

The product (1+x+x^2+x^3+...)(1+x^3+x^6+x^9+...)(1+x^5+x^10+.. .)... is the generating function for the number of partitions of n into odd parts.

How can you replace some of the plus signs with minus signs so that the resulting product when expanded has coefficients which are all either +1, zero, or -1?

(There are many solutions.)

Given the stucture of your factors you can work out how to do this step by step. I'm going to start with the original problem and successively replace "+" with "-" in the appropriate places. I'll leave it to you to find the pattern.

The original expression is:

(1+x+x^2+x^3+...)(1+x^3+x^6+x^9+...)(1+x^5+x^10+.. .) = 1 + ...
This will give us a leading term of (+)1, so we want the next term to be negative. The next term will come from the x in the first factor. There are no other terms that produce an x when we multiply this out, so change the sign on the x term in the first factor:

(1-x+x^2+x^3+...)(1+x^3+x^6+x^9+...)(1+x^5+x^10+...) = 1 - x + ...
The only way to produce an x^2 term is the third term in the first factor. We want this to be positive, so leave it alone.

(1-x+x^2+x^3+...)(1+x^3+x^6+x^9+...)(1+x^5+x^10+...) = 1 - x + x^2 + ...
There are two ways to produce the x^3: the fourth term in the first factor and the second term in the second factor. Now, isolate the terms
(1 + x^3 + ...)(1 + x^3 + ...)(1 + x^5 + ...)...
Recall that (1 + x^3)(1 - x^3) = 1 +0*x^3 - x^6
This eliminates the x^3 term. In the same fashion we wish to change one of the two signs in the x^3 terms in the problem. The question is which one? I would suggest that we have a pattern forming in the first factor where each term is "+ - + - ..." so I'm going to change that one.

(1-x+x^2-x^3+...)(1+x^3+x^6+x^9+...)(1+x^5+x^10+...) = 1 - x + x^2 +0*x^3 + ...

You should have the idea by now. If not let me know and I'll generate some more terms.

-Dan

Originally Posted by topsquark

Given the stucture of your factors you can work out how to do this step by step. I'm going to start with the original problem and successively replace "+" with "-" in the appropriate places. I'll leave it to you to find the pattern.

The original expression is:

(1+x+x^2+x^3+...)(1+x^3+x^6+x^9+...)(1+x^5+x^10+.. .) = 1 + ...
This will give us a leading term of (+)1, so we want the next term to be negative. The next term will come from the x in the first factor. There are no other terms that produce an x when we multiply this out, so change the sign on the x term in the first factor:

(1-x+x^2+x^3+...)(1+x^3+x^6+x^9+...)(1+x^5+x^10+...) = 1 - x + ...
The only way to produce an x^2 term is the third term in the first factor. We want this to be positive, so leave it alone.

(1-x+x^2+x^3+...)(1+x^3+x^6+x^9+...)(1+x^5+x^10+...) = 1 - x + x^2 + ...
There are two ways to produce the x^3: the fourth term in the first factor and the second term in the second factor. Now, isolate the terms
(1 + x^3 + ...)(1 + x^3 + ...)(1 + x^5 + ...)...
Recall that (1 + x^3)(1 - x^3) = 1 +0*x^3 - x^6
This eliminates the x^3 term. In the same fashion we wish to change one of the two signs in the x^3 terms in the problem. The question is which one? I would suggest that we have a pattern forming in the first factor where each term is "+ - + - ..." so I'm going to change that one.

(1-x+x^2-x^3+...)(1+x^3+x^6+x^9+...)(1+x^5+x^10+...) = 1 - x + x^2 +0*x^3 + ...

You should have the idea by now. If not let me know and I'll generate some more terms.

-Dan

The response is just what I am looking for. It's fine as far as it goes. The question is: How do you decide which changes to make. Some changes will lead to a blind alley, where no further choice can possibly satisfy the conditions of the problem.

Here's a choice of signs that will always work no matter how long you continue:

Take the first factor to be (1-x-x^2+x^3-x^4+x^5+x^6-x^7+...) Repeat this choice of signs in each of the other factors. Then the product, when expanded, will begin 1-x-x^2+x^5+x^7-...

What is the rule for the signs in each factor?

What does the expanded product look like as n-> infinity?

Originally Posted by Partition

The response is just what I am looking for. It's fine as far as it goes. The question is: How do you decide which changes to make. Some changes will lead to a blind alley, where no further choice can possibly satisfy the conditions of the problem.

Here's a choice of signs that will always work no matter how long you continue:

Take the first factor to be (1-x-x^2+x^3-x^4+x^5+x^6-x^7+...) Repeat this choice of signs in each of the other factors. Then the product, when expanded, will begin 1-x-x^2+x^5+x^7-...

What is the rule for the signs in each factor?

What does the expanded product look like as n-> infinity?

I didn't carry my work out far enough to prove my thesis but I suspect that the series I was developing was that the first factor has alternating signs and the other two factors are all "+"s. The pattern in the solution I was trying to force was a repeating pattern of +, - +, 0. (Whether that would work once I got up to the x^5 term and beyond is a question that I didn't work up to.)

I think that if you play with +/- patterns in the factors of your generating function you will be able to see one that works fairly easily. In this regard it would be nice if you have a calculator that can do the multiplications for you, just to save some time. If not, work the way I did previously in this thread, just change a few signs at the beginning of the series and see what happens.

-Dan