Combinatorics-binomial expansion?

[pupeye11]

Homework Statement

Let A(x) = \sum_{k>=0}a_{k}x^k and B(x) = \sum_{k>=0}b_{k}x^k show that:
A(X)B(X) = \sum_{k>=0}(\sum_{i=0}a_{i}b_{k-i})x^k

The second sum sign in the answer should be from i=0 to k.

The Attempt at a Solution

I factored out like terms and then multiplied them together and got

\sum_{k>=0}x^k(a_{k}b_{k}) then if i={0,1,2,...,k} we would get

\sum_{k>=0}x^k(\sum_{i=0}a_{i}b_{k-i})

I am guessing this is wrong?

 

[Tedjn]

Maybe I'm wrong, but isn't this by definition? What is your definition of polynomial multiplication?

 

[pupeye11]

to be honest i am not sure, i am quite lost in this class

 

[Tedjn]

Which class, and from where did this question come? It's possible all you're supposed to say is that a term with x^k clearly appears iff you multiply a term with xⁱ by a term with x^k-i, which gives you a coefficient of a_kb_k-i. Combining like terms gives you the sum...

 

[pupeye11]

It's an Intro to Combinatorics class and its from some homework that covers Binomial coefficients, the binomial theorem, and Newtons binomial theorem. That is the sections I believe the answer should come from out of all the choices I have. If you don't agree with that I can tell you the other sections we have covered for this homework.

 

[pupeye11]

I also don't get how your idea would work. I start with the two x^k therefor i never multiplied a x^i by an x^{k-i} so the coefficient wouldn't come about that way?

 

[Tedjn]

When you multiply two polynomials, you need to combine their individual terms in every way possible, so you will need to multiply the a_ixⁱ by b_k-ix^k-i sometime. It's possible for a_i or b_k-i to be 0.

 

[vela]

I also don't get how your idea would work. I start with the two x^k therefor i never multiplied a x^i by an x^{k-i} so the coefficient wouldn't come about that way?

It's often helpful to expand the summations to see what you're actually doing and where you're going wrong in your calculations. For example, suppose you had

A(x) = \sum_{k=0}^3 a_k x^k = a_0 + a_1 x + a_2 x^2 + a_3 x^3

B(x) = \sum_{k=0}^3 b_k x^k = b_0 + b_1 x + b_2 x^2 + b_3 x^3

Then

A(x)B(x) = (a_0 + a_1 x + a_2 x^2 + a_3 x^3)(b_0 + b_1 x + b_2 x^2 + b_3 x^3)

From this, you can see your first step of factoring like terms doesn't work in that there will be no terms that look like a_kb_kx^k except for k=0. Also, if you multiply it out, you should see a pattern for the coefficients in the final series.

 

[pupeye11]

alright, so if i expand A(x) i'll get something like

A(X) = a_{0}+a_{1}x+a_{2}x^2+...+a_{k}x^k?

then i do the same for B(X) and multiply them together?

 

[Tedjn]

Yes.

 

[pupeye11]

Ok, I got that answer then. The second part of the question says to use this result to find the coefficient of x^5 in the expansion of \frac{(x+y)^9}{1-x} and I do not get how the answer to the previous part is supposed to help me...

 

[vela]

Use A(x)=1/(1-x) and B(x)=(x+y)⁹. It looks like the book expects you to know how to write A(x) as a series.

 

[pupeye11]

Well A(x)=\frac{1}{1-x}=1+x+x^2+x^3+.... So this coefficient from x^5 is just going to be 1 but I don't know how to get the one from B(x)? Unless its not looking for the specific number which I would think that the coefficient would then be written as a_{1}b_{4}x^5. Would that be the solution to this problem?

 

[Tedjn]

Remember you are have a sum, of which a₁b₄ is certainly one part, but not all. Likely the book is looking for an expression involving y; you can find the coefficients for B(x) using binomial coefficients.

 

[pupeye11]

Ok then, so I can use Newton's binomial Theorem to find that

\sum_{k=0} nCr(9,5) x^5y^4 = 126 x^5y^4. Then I would have to add that 1 to give me 127 correct?

 

[Tedjn]

The summation sign you have there should not be there. Indeed, in (x+y)⁹, the coefficient in front of the x⁵ term is ₉C₅y⁴ (note the y in the expression). However, why would you add 1? Take a look again at the formula from the first part.

 

[pupeye11]

Alright I understand the B(X) part. The one would be added because when we change A(X) into the series the x^5 has a coefficient of one. Does it not?

 

[Tedjn]

I suggest, along the lines of vela's advice, to multiply out

(a₀ + a₁x + a₂x² + a₃x³ + a₄x⁴ + a₅x⁵)(b₀ + b₁x + b₂x² + b₃x³ + b₄x⁴ + b₅x⁵).​

See what pattern you can spot. It should help you get a feel for what the formula for multiplication is really saying.

 

[pupeye11]

When I multiplied that out the pattern I saw is the same one from before, that a_{i}b_{k-i}... sorry I really am not getting this. I understand that 126 is part of it though...

 

[Tedjn]

Yes, so what are b₀ through b₅ in B(x) = (x+y)⁹?

 

[pupeye11]

Would it be another 126 or am I completely lost now? :|

 

[Tedjn]

Can you expand (x+y)⁹ via the binomial theorem? There will be coefficients in front of x⁰, x¹, ..., x⁹. These correspond to the b₀ to b₉ of B(x), of which only b₀ to b₅ are needed in calculating the final coefficient you need. (Why?)

 

[vela]

It would really help if you post your attempts in sufficient detail rather than just ask seemingly random questions. It's hard to figure out where you're getting stuck, and we sometimes have to guess as to what you mean (like I have no idea what the 126 refers to). Keep in mind we don't know what you've tried, so even though a question may make complete sense to you, it doesn't to us.

 

[pupeye11]

It is because the coefficient that I am looking for is the one that is in front of x^5. So I would need the coefficients from all ones before and including x^5? Meaning that not only do I use nCr(9,5)=126 but add nCr(9,4)=126, nCr(9,3)=84. nCr(9,2)=36, nCr(9,1)=9, and nCr(9,0)=1. So those together give me 382?

 

[Tedjn]

So my last question is, is it really (x+y)⁹ and not something like (x+1)⁹?

 

[pupeye11]

it is definitely (x+y)^9

 

[vela]

You can't just add the numerical coefficients then because the coefficients b_k will contain different powers of y. For instance, b₁=(9c1)y⁸ while b₂=(9c2)y⁷.

 

[pupeye11]

Alright, that makes sense. Since I am looking for the coefficient of x^5 the answer would then be 9c5 y^4 = 126y^4?

 

[vela]

No, that would be the coefficient of x⁵ in B(x), not A(x)B(x). You'll still have a sum of the cross terms; you just can't simplify the sum.

 

[pupeye11]

Ok, so then for A(X)=\frac{1}{1-x}=1+x^2+x^3+x^4+x^5+... the coefficient of x^5 is 1. If all we care about are when we have x^5 wouldn't the coefficient of A(X)B(X) just be 126y^4 times 1?

 

[vela]

No, because, for example, the x² term in A(x) and the x³ term in B(x) will combine to contribute to the x⁵ term in A(x)B(x).

By the way, don't you see a contradiction in the answer you just gave, 126y^4, and the formula you verified earlier, which is a sum of a bunch of terms?

 

[pupeye11]

Yeah, I forgot about the sum... But if I was working with just B(x) then my answer would be 126y^4 but since I have A(x) I need to multiply together. Is there a theorem in combinatorics that makes this easy or do I just need to do it the long way?

 

[vela]

Well, there's the formula you verified earlier.

 

[pupeye11]

That is kind of the problem, I get that if I use the formula I'll have something that looks like this

\sum_{k>=0}(\sum_{i=0}^{k}a_{1}b_{4})x^5. How does this give me a number for a coefficient? Or do I take the coefficient at a_{1} and b_{4} and multiply them together. Then after doing that for all the combinations that create x^5 do I add them all together?

 

[vela]

How did you get this

\sum_{k>=0}(\sum_{i=0}^{k}a_{1}b_{4})x^5

from this

A(X)B(X) = \sum_{k>=0}(\sum_{i=0}a_{i}b_{k-i})x^k

The second sum sign in the answer should be from i=0 to k.

 

[pupeye11]

Yes, that came from the one you just copied and put above.

 

[vela]

I'm asking how you got the first from the second because they're inconsistent.

Expand this summation for k=5:

\sum_{i=0}^k a_i b_{k-i}

What do you get?

 

[pupeye11]

a_{0}b_{5}+a_{1}b_{4}+a_{2}b_{3}+a_{3}b_{2}+a_{4}b_{1}+a_{5}b_{0}

 

[vela]

Right, and that sum of six terms is the coefficient of the x⁵ term in A(x)B(x). In this case, all the a_i's are equal to 1. What are b_i's equal to?

 

[pupeye11]

The b_{i}'s are going to be b_{5}=nCr(9,5), b_{4}=nCr(9,4),b_{3}=nCr(9,3),b_{2}=nCr(9,2),b_{1}=nCr(9,1),b_{0}=nCr(9,0)?

 

[vela]

Not quite. Remember, the coefficient of x^k includes everything that multiplies x^k when you expand (x+y)⁹.

 

[pupeye11]

Are you trying to say I need the corresponding y's in there too, like b5 would have a y^4 and b4 would have a y^5, so on so forth? Otherwise I am not following you on this one.

 

[vela]

Yes, exactly.

 

[pupeye11]

Alright so the answer will be nCr(9,5)y^4+nCr(9,4)y^5+nCr(9,3)y^6+nCr(9,2)y^7+nCr(9,1)y^8+nCr(9,0)y^9 right? and thank you for all your help!

 

[vela]

Yup, that's it. Good work!