# A mathematical proof involving binomial coefficients and Pascal's Triangle **URL:** \ **Category:** Factual Questions\ **Created:** [January 4, 2004, 6:13am UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597 "2004-01-04T06:13:56Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![tFr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tFr](https://boards.straightdope.com/u/tFr)\ **Post date:** [January 4, 2004, 6:13am UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/1 "2004-01-04T06:13:56Z")
Hi, this is my first cool post to these forums. šŸ™‚ 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? Thanks for any feedback. šŸ™‚ ---
**Author:** ![KP](https://avatars.discourse-cdn.com/v4/letter/k/a9adbd/32.png) [@KP](https://boards.straightdope.com/u/KP)\ **Post date:** [January 4, 2004, 6:32am UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/2 "2004-01-04T06:32:53Z")
Welcome to the SDMB, tFr. 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. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [January 4, 2004, 6:37am UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/3 "2004-01-04T06:37:25Z")
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? ---
**Author:** ![tFr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tFr](https://boards.straightdope.com/u/tFr)\ **Post date:** [January 4, 2004, 6:54am UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/4 "2004-01-04T06:54:01Z")
Iā€™ve tried the following: a. Expressed the coefficients using summations: sum(from x=0 to n)[nCi], sum(from y=0 to k)[nCk], sum(from z=0 to n-k)[nC(n-k)], Then I expanded each one and tried to find some relation. No luck, as far as I could tell. b. Expanded the binomials and tried to find some relation among the three. Still nothing, because the n-k is really getting on my nerves. **KP** : Sorry I didnā€™t know about it before ā˜¹ ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [January 4, 2004, 8:16am UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/5 "2004-01-04T08:16:56Z")
> [@](#): > > \*Originally posted by tFr \* > a. Expressed the coefficients using summations: > > sum(from x=0 to n)[nCi], sum(from y=0 to k)[nCk], > sum(from z=0 to n-k)[nC(n-k)], > > Then I expanded each one and tried to find some relation. No luck, as far as I could tell. 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? ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [January 4, 2004, 3:23pm UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/6 "2004-01-04T15:23:06Z")
Umā€¦ What may be fouling you up is that the problem should probably read (bolding mine): > [@](#): > > "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 Ā®." 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. ---
**Author:** ![tFr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tFr](https://boards.straightdope.com/u/tFr)\ **Post date:** [January 4, 2004, 8:00pm UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/7 "2004-01-04T20:00:30Z")
@ **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)], Oops sorry. ---
**Author:** ![Q.E.D](https://avatars.discourse-cdn.com/v4/letter/q/51bf81/32.png) [@Q.E.D](https://boards.straightdope.com/u/Q.E.D)\ **Post date:** [January 4, 2004, 8:22pm UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/8 "2004-01-04T20:22:30Z")
> [@](#): > > \*Originally posted by KP \* > **I regret to inform you that ā€œhomework questionsā€ are generally frowned upon here. Just FYI.** 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. ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [January 4, 2004, 8:28pm UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/9 "2004-01-04T20:28:41Z")
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ā€¦ ---
**Author:** ![tFr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tFr](https://boards.straightdope.com/u/tFr)\ **Post date:** [January 4, 2004, 8:41pm UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/10 "2004-01-04T20:41:00Z")
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. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [January 4, 2004, 9:17pm UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/11 "2004-01-04T21:17:24Z")
Yes, try doing it assuming that - should be a +. Even if itā€™s not a typo, youā€™ll make a whole lot of progress toward the right answer. ---
**Author:** ![tFr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tFr](https://boards.straightdope.com/u/tFr)\ **Post date:** [January 4, 2004, 9:17pm UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/12 "2004-01-04T21:17:30Z")
Now Iā€™m trying: 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)], and Iā€™m going to liberally use the identity nC(r-1) + nCĀ®= (n+1)CĀ®. Stay tuned, this may be a breakthrough! ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [January 5, 2004, 12:34am UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/13 "2004-01-05T00:34:50Z")
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. ---
**Author:** ![tFr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tFr](https://boards.straightdope.com/u/tFr)\ **Post date:** [January 5, 2004, 11:23pm UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/14 "2004-01-05T23:23:39Z")
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) (n+k) C Ā®+(kC(r+1))=(n+k) C (r+1) Dead. Anyone? Tips? DOOOOOOOOOOOOOOOOOOOOOOMED ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [January 5, 2004, 11:41pm UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/15 "2004-01-05T23:41:22Z")
Very very close. Think about it this way: you have the equation > [@](#): > > (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)) 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. ---
**Author:** ![tFr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tFr](https://boards.straightdope.com/u/tFr)\ **Post date:** [January 5, 2004, 11:45pm UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/16 "2004-01-05T23:45:37Z")
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. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [January 5, 2004, 11:51pm UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/17 "2004-01-05T23:51:50Z")
> [@](#): > > \*Originally posted by tFr \* > The proof now comes to this: > > (n+k) C (r+1) = (n+k) C Ā® + k C (r+1) 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.) ---
**Author:** ![tFr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tFr](https://boards.straightdope.com/u/tFr)\ **Post date:** [January 6, 2004, 1:38am UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/18 "2004-01-06T01:38:02Z")
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. O\_o ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [January 6, 2004, 1:53am UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/19 "2004-01-06T01:53:01Z")
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. ---
**Author:** ![tFr](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@tFr](https://boards.straightdope.com/u/tFr)\ **Post date:** [January 6, 2004, 7:07am UTC](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597/20 "2004-01-06T07:07:50Z")
Coefficients of these x^2 terms are sum(from z=0 to 2)[(k C z)(n C (2-z)], correct? I show: Based on: (1+nx)(1+kx)=ā€¦knx^2 1(1+nx+\*nC2)x^2)=ā€¦nC2 x^2 1(1+kx+\*kC2)x^2)=ā€¦kC2 x^2 -\>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]. O\_O [Next page](https://boards.straightdope.com/t/a-mathematical-proof-involving-binomial-coefficients-and-pascals-triangle/222597.md?page=2)