Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving combinatorics identities

  1. Jan 6, 2009 #1
    Is it always possible to prove combinatorial identities in a brute force way, as opposed to the preferred way of seeing that the RHS and LHS are two different ways of counting the same thing? For example, the identity

    [tex] \left (^{n-1}_{k-1}\right) + \left (^{n-1}_{k}\right) = \left (^{n}_{k}\right)[/tex]

    can be seen either from the counting interpretation of 'n choose k' or by writing the binomial coefficients explicitly in terms of factorials and adding fractions, which is the brute force way. In the slightly more complicated identity

    [tex]\sum_{k=0}^{m}\left (^{a}_{k}\right) \left (^{b}_{m-k}\right) = \left (^{a+b}_{m}\right)[/tex]

    can you prove that without using the fact that the RHS and the LHS are two ways of counting the number of ways of choosing m objects from a+b objects?
  2. jcsd
  3. Jan 10, 2009 #2
    The proof isn't too hard if you set it up right. Consider two sets [itex]A[/itex] and [itex]B[/itex] [edit: two disjoint sets] where [itex]|A| = a[/itex] and [itex]|B| = b[/itex]. We want to choose [itex]m[/itex] elements from the set [itex]A \cup B[/itex]. If we want [itex]k[/itex] of the elements to be from [itex]A[/itex], how many options do we have?
    Last edited: Jan 10, 2009
  4. Jan 10, 2009 #3
    Yes, that is the combinatorial proof, which I am aware of (sorry for not being clear about that). Is there a more brute force, algebraic sort of way to prove it? Preferably an approach that works generally for combinatorial identities. I know that combinatorial proofs are preferable because they give the most insight, but what about when you can't think of a combinatorial proof? Is there a general way to proceed? For example, this identity

    [tex]\sum_{k=1}^{n}\frac{\left( ^{2n-2k}_{n-k}\right)\left( ^{2k}_{k}\right)}{2k-1}=\left( ^{2n}_{n}\right)[/tex]

    seems to be true, but I don't immediately see a combinatorial argument for it. I wonder how the symbolic math solvers do it. Maybe it's just all pre-programmed lookup tables.
  5. Jan 16, 2009 #4
    You could use induction.
  6. Jan 19, 2009 #5
    I've tried to prove that last identity by induction but couldn't figure out how. Is it generally possible to prove these identities by induction? Thanks.
  7. Apr 10, 2010 #6
    The second identity can be proven by first recognizing that

    [tex](x+y)^n=\sum_{k=0}^{n} x^{k} y^{n-k} \left _n C _k [/tex]

    then use the fact that

    [tex](x+y)^{a+b}=(x+y)^{a} (x+y)^{b}[/tex]

    Expand the terms using the summation form, then compare like terms to obtain your identity.
  8. Apr 10, 2010 #7
    What you are looking for is called "generating functions" and it's a topic from the larger field of Algebraic Combinatorics, whose aim is to develop systematic methods (even algorithmic) to prove these identities. This paper is a good introduction, if you're interested:

    http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enuPCM.pdf" [Broken]

    Another one is Wilf and Zeiberger's book A = B, available here:

    http://www.math.upenn.edu/~wilf/AeqB.html" [Broken]
    Last edited by a moderator: May 4, 2017
  9. Apr 30, 2010 #8

    Okay, that makes a lot of sense. Thank you! I think this is an example of the generating function approach recommended by JSuarez. And thanks for digging up this post of mine. I had recently come back to counting, this time in connection with random walks. So it is perfect timing for me to think about these things again.

    Awesome. Thank you for those excellent (and free :smile:) resources!
    Last edited by a moderator: May 4, 2017
  10. Apr 30, 2010 #9
    It is. The binomial theorem, in the form [itex]\left(1+x\right)^n[/itex], is the generating function for the binomial numbers with integer upper index [itex]n \geq 0[/itex] (and this also applies to more general binomial numbers).

    One more thing: if the problem you are working at involves counting paths with specific properties, then you will need generating functions, and I can recommend you another source (not free): Stanley's "Enumerative Combinatorics", particularly vol. I.
  11. Apr 30, 2010 #10
    Cool. I'll see if I can get it through interlibrary loan. I am trying to think of other ways to prove the result that for paths of length 2n, the number of paths with 2k edges above the time axis is the same as the number of paths whose last return to zero is at time 2k. They both have the discrete arcsine distribution. Feller, Vol I. has a neat inductive proof, but I would really like a bijective proof or even one using generating functions.
  12. Jun 2, 2010 #11
    This is identity 3.92 on p. 37 of

    Henry W. Gould, Combinatorial Identities, 1972


  13. Jun 2, 2010 #12
    i don't understand what the problem is? the identities presented in the OP are proven by writing down what the choose coefficients are in terms of factorial and manipulating a little aren't they?
  14. Jun 2, 2010 #13
    Another resource is Wilf's book "generatingfunctionology", which can be downloaded for free:


    It doesn't cover as much material as Stanley's book, but it's more fun. Wilf's enthusiasm is contagious.
  15. Jul 8, 2010 #14
    gburdell1 already gave a generating function proof of this one. Here is an example of using generating functions to prove a similar but slightly harder identity:

    [tex]\sum_{k=0}^{n}\binom{k}{r}\binom{n-k}{m-r} = \binom{n+1}{m+1}[/tex]

    First define the sequence of generating functions

    [tex]f_r(x) = \sum_{k \geq 0} \binom{k}{r}x^k[/tex]

    and note that the sum in question is just the coefficient of x^n in fr(x) fm-r(x):

    [tex]\sum_{k=0}^{n}\binom{k}{r}\binom{n-k}{m-r} = [x^n]f_r(x)f_{m-r}(x)[/tex]

    To find the form of the f_r, find a recurrence relation that they satisfy.

    [tex]f_r(x) = \sum_{k \geq 0} \binom{k}{r}x^k = \sum_{k \geq 1} \left[ \binom{k-1}{r-1}+\binom{k-1}{r} \right]x^k[/tex] for r>0

    [tex]f_r(x) = x(f_{r-1}(x)+f_r(x))[/tex] or

    [tex]f_r(x) = \frac{x}{1-x}f_{r-1}(x)[/tex] for r>0

    Note that f_0(x) = 1+x+x^2 + .... = 1/(1-x). Therefore the solution to the recurrence is

    [tex]f_r(x) = \frac{x^r}{(1-x)^{r+1}}[/tex]

    Going back to the combinatoric identity, we are looking for

    [tex][x^n]f_r(x)f_{m-r}(x) = [x^n]\frac{x^m}{(1-x)^{m+2}}[/tex], which is independent of r.

    [tex][x^n]f_r(x)f_{m-r}(x) = [x^{n-m}]\frac{1}{(1-x)^{m+2}} = \binom{(n-m)+(m+2)-1}{(m+2)-1}[/tex]

    If you read the original post, you will see that is exactly what the OP was asking.


    For an interpretation of this identity, which I recently encountered, see this thread:


    Basically, you got a room full of n+1 people and you want to choose m+1. One way to do it is to condition on the r+1st youngest chosen person. Thanks to Hurkyl for explaining that one.
    Last edited: Jul 8, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook