proving combinatorics identities

Adeimantus

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?

qntty

The proof isn't too hard if you set it up right. Consider two sets [latex]A[/latex] and [latex]B[/latex] [edit: two disjoint sets] where [latex]|A| = a[/latex] and [latex]|B| = b[/latex]. We want to choose [latex]m[/latex] elements from the set [latex]A \cup B[/latex]. If we want [latex]k[/latex] of the elements to be from [latex]A[/latex], how many options do we have?

Adeimantus

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.

daveyinaz

You could use induction.

Adeimantus

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.

gburdell1

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.

JSuarez

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/~zeilber...PDF/enuPCM.pdf

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

http://www.math.upenn.edu/~wilf/AeqB.html

Adeimantus

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 ) resources!

JSuarez

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.

Adeimantus

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.

hflanders

This is identity 3.92 on p. 37 of

Henry W. Gould, Combinatorial Identities, 1972

HF

ice109

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?

awkward

Another resource is Wilf's book "generatingfunctionology", which can be downloaded for free:

http://www.math.upenn.edu/~wilf/DownldGF.html

It doesn't cover as much material as Stanley's book, but it's more fun. Wilf's enthusiasm is contagious.

techmologist

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 f_r(x) f_m-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.

EDIT:

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

http://www.physicsforums.com/showthread.php?t=413843

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+1^st youngest chosen person. Thanks to Hurkyl for explaining that one.