Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite
1

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"?

share|improve this question
I think that as long as Pascal's Triangle is well explained and well understood it can be used freely...at least up to some definite level (high school or stuff, I guess) – DonAntonio Apr 30 at 12:52
1  
This is a question about grading policy, and is thus highly dependent on who's doing the grading. – vadim123 Apr 30 at 13:47
It's quite unclear what you mean by a combinatorical proof.. Everything which holds by showing Pascals triangle also holds if using known identities for binomial coefficients? – malin Apr 30 at 14:26
@malin That is more or less exactly my question. What counts and what doesn't count as a combinatorial proof? I also tagged it as a soft-question to encourage personal opinions. – Arthur Apr 30 at 14:47

2 Answers

up vote 1 down vote accepted

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?"

share|improve this answer
up vote 1 down vote

I would argue that a combinatorial proof is something more substantial than pointing out a pattern in a picture! If we are at the level of "combinatorics" then we are also at the level of proofs and as such, the phrase "combinatorial proof" asks for a proof but in the combinatorial (or counting) sense.

A proof by example, i.e. "this pattern holds in the small portion of Pascal's Triangle that I have drawn", is not a proof period, combinatorially or otherwise. The general case of such a property could be verified combinatorially, but simply observing it would not constitute a combinatorial proof in itself. At least that's the way I see it.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.