I have an analytical paper to write for my math class, and one step ground me to a halt:
"By comparing the corresponding coefficients of the expansions of (1+x)^n(1+x)^k and (1+x)^(n-k), show that
sum(from z=0 to k)[(k C z)*(n C (r-z))]=(n+k) C (r)
The capital C’s are of nCr, which gives the value of the number in row n, number r of Pascal’s Triangle.
Although I have already tried very hard to come up with a proof, I am stumped beyond recognition. I have never been so thoroughly owned. I’m not really requiring that you give me a complete proof; I’m asking that you give me some tips, some breakthroughts?
I regret to inform you that “homework questions” are generally frowned upon here. Just FYI.
However, I don’t think I’d be out of line giving you this tip: do a few expansions and notice why the coefficients are what they are, then look at Pascal’s triangle and ask why those coefficients are what they are. I think you’ll see the relationship quickly.
From the sound of it, you don’t know where to begin. Is that true? If you’ve made any progress at all, tell us. Then we can help you better.
KP’s method sounds simple, but I don’t see how it helps. So, maybe that’s the best thing to do. I don’t know.
But here’s how I thought about it. You know that (1+x)[sup]n[/sup] (1+x)[sup]k[/sup] = (1+x)[sup]n+k[/sup], right? Each of those three things, expanded, is a polynomial whose coefficients you know. And the product of the first two must equal the third. Is that the tree you’ve been barking up?
Okay, what are those summations supposed to represent? The coefficients themselves? Shouldn’t x, y, and z appear somewhere in there? What’s i? I think the first one is supposed to look something like this: SUM(x=0…n) [nCx]
I think you may be on the right track, but you’re mixing up your notation. Can you try writing it again very carefully?
Um… What may be fouling you up is that the problem should probably read (bolding mine):
I don’t know if this is just an error in what you typed in or whether your teacher/professor gave it wrong, but you said that the “(n-k)” was giving you difficulty when it shouldn’t really be there.
@MikeS: That was the problem, verbatim. It said n-k. Judging from the general quality of the copy I got, it shouldn’t be printed wrong. Though I can’t rule out a problem at the source of my copy.
@Achernar:
sum(from x=0 to n)[nCx], sum(from y=0 to k)[nCy],
sum(from z=0 to n-k)[(n-k)C(z)],
Not at all. What we do frown upon are people trying to get homework questions done by deceit. Asking for help honestly, showing what efforts have been made so far, and making a genuine effort to do the work oneself is fine.
Well, then, I’m stymied. I can do it in about five lines if it’s (n+k), but if it’s (n-k) it doesn’t make any sense to be comparing coefficients between two polynomials that aren’t equal. My money’s on a typo at this point, but I’ll see if I can figure something else out…
Hmm, I never seriously considered it a typo before. I’ve been grinding away for days. If this really is a typo, someone’s gonna find that the domain of their rectum has just expanded and intersected with a higher-dimensional space.
It’s definitely n+k you need to consider. Remember, if two polynomials are equal, then the coefficients of x, x[sup]2[/sup], …, x[sup]r[/sup],… are equal in those two polynomials. Combine this idea with Achernar’s first hint.
By the way, it was a typo. n-k should have been n+k.
kills bureaucrats who made this possible
I mad esome headway, now that I got that crap out of the way. This isn’t math class, this is a field course in how to get screwed.
The proof now comes to this:
(n+k) C (r+1) = (n+k) C ® + k C (r+1)
I arrived at it using the following:
(1+x)^k(1+x)^n = (1+x)^(n+k)
(1+kx+(k C 2 )(x^2)…x^k)(1+nx+n C 2 (x^2)…x^n)=(1 + (n+k)x +…x^(n+k))
Corresponding coefficients must be equal:
Cx^r = Dx^r
Base case for x^1:
(n+k)x=nx+kx=x((kC0)(nC1)+(kC1)(nC0)) which equals x(n+k) C 1.
Which fits
sum(from z=0 to k)[(k C z)*(n C (r-z))]=(n+k) C ®
Did it for x^2 also. Base case.
Arrived at a hypothesis:
sum(from z=0 to r)[(k C z)(n C (r-z))]=(n+k) C ®
Induction:
sum(from z=0 to r+1)[(k C z)(n C (r+1-z))]=(n+k) C (r+1)
sum(from z=0 to r)[(k C z)*(n C (r-z))]+(nC0)(kC(r+1))=(n+k) C (r+1)
Very very close. Think about it this way: you have the equation
Suppose you were to multiply out the left-hand side of the equation. How could you get, say, an x^2 term? Well, there would be three of them: One from where the x^0 term of the first polynomial multiplies the x^2 term of the second polynomial; one where the x^1 term of the first multiplies the x^1 term of the second; and one where the x^2 term of the first multiplies the x^0 term of the second. What would the coefficients of each of these three terms be?
Once you’ve figured that out, you should be able to generalize from x^2 to x^r.
Yeah, I got that part, but before I just deemed it wayy too complicated combinatorically to sort that out. Thanks for pointing it out to me; I’ll definitely go down that path.
Just to warn you, but this equation just isn’t so. You can check these by using a couple of sample values. For n = k = r = 1, you get:
2C2 = 2C1 + 1C2
1 = 2 + 0
I agree with MikeS, and I don’t think that you need to use induction unless you mean to be ultra-rigorous. That is, I think that you can just state the value of C without proving it via induction. (Where C is the coefficient of the x[sup]r[/sup] term on the left-hand side.)
Wow. You can declare something proven using just a few cases then a generalizing rule? I never knew that. Being a n00b to the math world isn’t all bad.
No, that’s not the best way to do it. Don’t generalize from a few cases. But notice how MikeS was able to describe the x[sup]2[/sup] term without induction? Think along those lines.
->that’s all the x^2 terms there are on the left side, therefore
(kC2)x^2 + knx^2 + (nC2)x^2
=(kC2)x^2 + (kC1)(nC1)x^2 + (nC2)x^2
=sum(from z=0 to 2)[(k C z)(n C (2-z)]x^2=(n+k)C(2)x^2
since Bx^r=Cx^r where B is an element of the set {sum(from i=0 to n)[(n C i)]*sum(from j=0 to k)[(k C j)]} and C is an element of the set sum(from z=0 to n+k)[(n+k)Cz].
