(A new question of the week)
A question from last August gave us some nice problems reminiscent of the Binomial Theorem, which were very deserving of discussion.
Three problems
The question came from Arsh:
I have some coefficient problems which I am unable to solve. I don’t know if a single concept will work for all so I am stating them.
Q1) Find the coefficient of x^203 in the expression (x – 1)(x^2 – 2)(x^3 – 3) … (x^20 – 20)
Q2) Find the coefficient of x^49 in the product (x – 1)(x – 3)(x – 5)(x – 7) … (x – 99)
Q3) Find the coefficient of x^9 in the expansion of (1 + x)(1 + x^2)(1 + x^3) … (1 + x^100)
Please explain through these topics: Binomial theorem, or sequence and series, or permutations and combinations.
This is a well-planned question, listing several questions together in case one should provide hints for another, and telling us what methods are expected to be used. This turned out to be very helpful.
There are some areas of combinatorics that I have never learned, and at first glance I thought these might require them (though the question implied they should not). As a result, I left the question for others to take … until I realized I had something good to write about:
Hi, Arsh.
When I first saw these, I assumed they are all quite difficult, because the first one looks especially hard. I was waiting for someone who knows some more advanced methods to answer. But when I scanned all three again, to see if they were all the same, I realized that the third is much nicer than I thought, and I quickly solved it, using basic combinatorial thinking. Then I took a closer look at the second, and realized that it, too, is an “easy” case of its type. I haven’t yet seen what makes the first one solvable! But let’s look at the third:
Find the coefficient of x^9 in the expansion of (1 + x)(1 + x^2)(1 + x^3) … (1 + x^100).
It is not uncommon that a difficult type of problem includes special cases can be given to students who are not prepared for the general case. Rather than special knowledge, it requires creative application of the basics. All it takes, that is, is a reason to hope I will be able to do it! (This is advice I often give to students: Just try something, and you may discover that you have a better idea than you knew. You don’t have to know ahead of time all the steps you will be taking.)
Starting with the easy one
One way to start, if you are unfamiliar with this sort of problem, is to try a simpler case. Consider, for example, at \((1+x)(1+x^2)(1+x^3)\), which expands to $$(1+x+x^2+x^3)(1+x^3) =\\ 1+x+x^2+x^3+x^3+x^4+x^5+x^6 =\\ 1+x+x^2+2x^3+x^4+x^5+x^6$$ Each term (before combining like terms) comes from a product of some subset of the terms \(x\), \(x^2\), and \(x^3\) (with a 1 from the other factors); and any term with exponent less than 3 must not have \(x^3\) as one of its factors. We are looking for the coefficient of \(x^9\), so all factors after \(1+x^9\) will be contributing only their 1. So:
How can you make a term with x^9? By multiplying together terms whose exponents add up to 9, right?
The first thing I realized is that we won’t be using any of the factors beyond x^9, so the problem might as well be
Find the coefficient of x^9 in the expansion of (1+x)(1+x^2)(1+x^3)… (1+x^9).
Do you see why that doesn’t change the problem?
Suddenly it’s a smaller problem than it seemed, and feels more doable. Now we think about where the specific terms in the expansion with exponent 9 come from:
Now, notice that the terms we will be using will look like (x)(x^3)(x^5), with exponents that sum to 9 and are all different (since each exponent can appear only once in the product).
So the problem reduces to this question:
In how many ways can we express 9 as a sum of distinct natural numbers?
Suddenly this is “just” a combinatorial problem. That can still be hard, but in this case is not:
Now, there may be a nice way to use combinations or something to calculate this, but the number is small enough to just list the sums, and that’s going to be less work than a more elaborate (and general) method. So try doing that. (I think the key to these problems is exactly that they are not general cases, but are special.)
Let me know what you find; and then while you wait for an answer (from me or someone else), give #2 a try, using similar ways of thinking. Look for what makes it easier than it could be. The first may turn out to be different from those; I don’t know yet.
Sometimes we can feel like it isn’t real math unless we have used a general method; but that is false. We’ve done plenty of good mathematical thinking by just turning the problem into a counting problem.
We’ll get back to #3 later.
Seeing the simplicity in the harder ones
Two and a half days later, Arsh had not yet replied, but I had more to say:
Hi again, Arsh.
Just to keep you up-to-date, I have solved the first problem; the key is to find what combinations of powers have to be excluded. It is, as I thought, a little harder than the others, so the order I suggested for solving them is appropriate.
I look forward to discussing these with you, so please let me know what you’ve found, even if you don’t think you’re close — or if you think you’ve solved them all.
Once again, a student may think his work is not worth showing, but it may take just a little hint to turn apparent failure into resounding success. So I encouraged showing any work at all, to get the conversation moving forward.
Now Arsh answered:
Ok, I get it that the last one was very easy. We can get 9 from (1, 8) (2, 7) (3, 6) (4, 5) (1, 2, 6) (1, 3, 5) (2, 3, 4) (9, 0).
So, I think the coefficient would be 8.
In the second one I get the highest power as x^50 so x^49 would the sum of roots which are 1, 3, 5, 7, …, 99.
So, sum of first 50 odd numbers is 50² = 2500. So coefficient would be -2500.
Then in the first one, 7 powers have to be excluded as max power is 210. So no. of ways in which 7 can be made as the sum of distinct natural numbers is (7, 0) (1, 6) (2, 5) (3, 4) (2, 4, 1).
This much I have done. I am still wondering why we are excluding powers in 1st one. Please explain how to solve the first one.
See if you can follow Arsh’s thinking, before looking below for my elaborations. He has done well.
Now I could go through each problem in detail, showing Arsh’s work, commenting on it, and demonstrating how I would express it:
Problem 3: Counting sums to 9
Hi, Arsh.
(#3) Find the coefficient of x^9 in the expansion of (1 + x)(1 + x^2)(1 + x^3) … (1 + x^100)
“We can get 9 – (1, 8) (2, 7) (3, 6) (4, 5) (1, 2, 6) (1, 3, 5) (2, 3, 4) (9, 0)
So, I think the coefficient would be 8.”
Good work. Since each term of the expansion before simplifying is a product of some 1’s and some distinct powers of x, the coefficient of the x^9 term is the number of these terms, which is the number of ways to get 9 as a sum of distinct positive integers, which you have listed. I would give the list this way (I found them by starting with the largest number in each case):
9
8+1
7+2
6+3
6+2+1
5+4
5+3+1
4+3+2
Since there are 8 of these, that is the desired coefficient. This was easy because of the 1’s, and the relatively small exponent.
I find it easier to be certain of the answer when making a list like this, if I make it an orderly list, following some consistent order to avoid missing anything. Arsh started out increasing the first number, then apparently filled in some missed cases.
If we had tried to do this by a formula, we would find that we are counting “unordered partitions of the number 9 with distinct integers”, which is not pretty (there is no nice formula). In fact, one way to do it is to turn this problem inside-out, using our product as a generating function and finding the coefficient of the \(x^9\) term! For an introduction to the topic, and an example not quite like this one, see
Partitioning the Integers Number of Unordered Partitions
It is definitely easiest just to list and count!
Problem 2: The next-to-last term
(#2) Find the coefficient of x^49 in the product (x – 1)(x – 3)(x – 5)(x – 7) … (x – 99)
“I get the highest power as x^50, so x^49 would the sum of roots which are 1, 3, 5, 7, …, 99.
So, sum of first 50 odd numbers is 50² = 2500. So coefficient would be -2500.”
Good, again. This turned out to be easy once I saw that there are 50 factors, so the x^49 term is the next-to-last; it is the sum of terms each of which is the product of 49 -1’s and only one x, namely -99x + -97x + … + -1x = -2500x. You could have done the sum as an ordinary arithmetic series, but seeing it as the sum of odd numbers is even nicer. And connecting this to the fact that the second-highest degree term has the (negative) sum of roots as its coefficient is even better.
To find a coefficient in the middle of this long polynomial would be quite difficult, but one near the beginning or end is easy.
My approach was simply to see that the terms in the expansion containing \(x^{49}\) would be formed by multiplying all but one of the x‘s, and therefore using each of the constants as the coefficient of one term; the combined term would have as its coefficient the sum \(-1 + -3 + -5 + \dots + -97 + -99\), which I added using the formula $$\frac{\text{first + last}}{2}\times n = \frac{-1 + -99}{2}\times 50 = -2500$$
Arsh showed his mastery of the material by taking a more advanced perspective, knowing that (a) the linear term of a polynomial is the negative of the sum of its zeros, and (b) the sum of the first n odd numbers is the square of n, that is, $$\sum_{i=1}^{n}(2n-1) = n^2$$ so that the sum is just \(-50^2 = -2500\).
For examples of finding the sum of consecutive odd numbers either way, see:
General Approach for Sum of Arithmetic Series Adding Arithmetic Sequences Summing Odd Numbers Geometrically
Problem 1: Excluding sums to 7
Now for the hard one:
(#1) Find the coefficient of x^203 in the expression (x – 1)(x^2 – 2)(x^3 – 3) … (x^20 – 20)
“7 powers have to be excluded as max power is 210 .So no. of ways in which 7 can be made as the sum of distinct natural numbers is (7, 0) (1, 6) (2, 5) (3, 4) (2, 4, 1) .
This much I have done. I am still wondering why we are excluding powers.”
I think you got the main idea I was communicating in my hint. Each term in the expansion is the product of some powers of x and the negatives of the exponents of the excluded powers (e.g. when x^2 is not used, -2 is).
Since the degree of the polynomial is the sum of integers from 1 to 20, namely 210, and we want the x^203 term, we are adding up terms that exclude powers that add up to 7, as you say.
So for each way to get 7 as a sum, the coefficient we use is the product of those numbers. For example, the term formed by multiplying all factors except (x – 1) and (x^6 – 6) is (-1)(-6)x^(210 – 7).
Note that the sign of the coefficient is positive when we multiply an even number of factors, and negative when there are an odd number.
As an example, one term with \(x^{203}\) will be obtained by multiplying \(-7\) by the power of x in each of the other 19 factors: $$(x^1)(x^2)(x^3)(x^4)(x^5)(x^6)(-7)(x^8)(x^9)(x^{10})(x^{11})(x^{12})(x^{13})(x^{14})(x^{15})(x^{16})(x^{17})(x^{18})(x^{19})(x^{20}) = -7x^{203}$$ And another term will use the constants from factors with exponents 1 and 6: $$(-1)(x^2)(x^3)(x^4)(x^5)(-6)(x^7)(x^8)(x^9)(x^{10})(x^{11})(x^{12})(x^{13})(x^{14})(x^{15})(x^{16})(x^{17})(x^{18})(x^{19})(x^{20}) = 6x^{203}$$
Now you can make a table listing your sets of numbers and their products, and see what you get. (But be careful counting the number of factors — there’s a reason I listed as I did in #3, not including 0.)
When you finish, see here to check!
Here is my list (which Arsh had right, apart from inappropriately including 0 with 7, which would have made the product zero):
7
6 + 1
5 + 2
4 + 3
4 + 2 + 1
That’s all there are. So the five terms with degree 203 are \((-7)x^{203}\), \((-1)(-6)x^{203}\), \((-5)(-2)x^{203}\), \((-4)(-3)x^{203}\), and \((-1)(-2)(-4)x^{203}\); adding them up, the coefficient is \(-7 + 6 + 10 + 12\ – 8 = 13\).
The link I provided is to WolframAlpha’s expansion of the polynomial:
$$\prod_{k=1}^{20}(x^k – k) = x^{210} – x^{209} – 2 x^{208} – x^{207} – x^{206} + 5 x^{205} + x^{204} + \mathbf{13 x^{203}} + 4 x^{202} + 2 x^{200} – 8 x^{199} + … $$
The coefficient we want is, indeed, 13.
This one was harder because (a) the exponent we need is large rather than small as in #3; (b) the constant terms are not all 1 as in #3; and (c) the exponents in the factors are not all 1 as in #2. But it is still relatively easy because the term is near one end of the expansion. A middle term, like x^100, would be unpleasant!
These are very nice problems. You should thank whoever made them up.
A problem that makes you think deeply is a good problem. More math should be taught this way!