Re: Explanations

[David Yetter <dyetter@math.ksu.edu>]

My private reply to the original query from Jean-Pierre Marquis pointed
to the style of combinatorial proof you refer to:  they are called "bijective" or
"combinatorial"  proofs depending on the author, and rely on giving
interpretations of "big ugly formula_1" and "big ugly formula_2" as enumerating
the same thing by different means.

For instance on can prove that

n*2^{n-1} = \sum_{k=1}^n k*C(n,k)

(writing C(n,k) for the binomial coefficient "n chose k") by differentiating the
binomial theorem and evaluating at 1, but this hardly seems to explain it.

Better is to observe that both sides count the number of ways to select a 
subset with a distinguished element from an n element set, the LHS by
selecting the distinguished element, then the rest of the subset, the RHS
by choosing a cardinality k for the subset, selecting the subset then selecting
the distinguished element from the subset.

David Y.


On 22 Apr 2011, at 08:55, Graham White wrote:

> And the folklore is (I haven't checked this in a proper history book)
> that Gauss proved quadratic reciprocity numerous times because he didn't
> consider the proofs sufficiently explanatory. It's certainly true that
> modern proofs (i.e. those using the methods of algebraic number theory)
> generalise it, and thereby explain, for example, what it is about the
> rationals, and the number two, that makes primes in the rationals obey
> quadratic reciprocity. I think one conclusion here is that, if you say
> "explanatory", I am entitled to answer "so what do you want explained?"
> 
> Another point is this: there are lots of combinatorial
> identities of the form
> 
> big ugly formula_1 = big ugly formula_2
> 
> which can be proved directly (for example, by induction
> and a lot of algebra), but where the proof is utterly unilluminating.
> And in many cases there are more conceptual proofs which people
> generally find more illuminating (depending on taste, of course).
> 
> Graham
> 

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]