[Math] Pascal’s triangle and combinatorial proofs

combinatoricssoft-question

This recent question got me thinking, if a textbook (or an exam) tells a student to give a combinatorial proof of something involving (sums of) binomial coefficients, would it be enough to show that by Pascal's triangle these things do add up, or would you fail an answer like that? What if we didn't call it Pascal's triangle but "the number of paths that stop at some point at step $i$ during a one-dimensional random walk"?

Best Answer

In the context of your question, talking about textbooks or exams, this could be viewed as a question of pedagogy. There are a couple of reasons why an author or an instructor would introduce combinatorial proofs, particularly those involving binomial coefficients:

  • To reinforce the notion that binomial coefficients can be used to count the number of ways some things can occur. A combinatorial proof of an identity involving binomial coefficients can thus provide a means by which the author can get his of her audience to do the same counting task in two different ways: two counting problems in a single exercise.
  • To illustrate the importance of the idea that some identities are quite a bit easier if approached from a counting perspective than by algebraic manipulation.

A good example of the latter is the well-known identity $$ \sum_{k=0}^n\binom{n}{k}=2^n $$ One could do this by induction on $n$, but the algebraic proof is nowhere as simple (and illustrative) as the purely combinatorial version.

To answer your question, then, I'd recommend one of two strategies. First, if this is a course and you were posed such a question, the best way would be to ask your instructor something like "I could answer this question by using properties of Pascal's Triangle; would you accept that or do you want a combinatorial proof from the ground up?" If such a question would be considered out of bounds or if you were self-studying, you might ask yourself, "What was the author's likely intent here, to have me get the answer by any means possible or was it to encourage me to think combinatorially?"