Quantum Tecniques/Gen Functions- don't be afraid of new techniques

Ronald de Wolf gave a GREAT talk at CCC on the uses of Quantum techniques to Classical Problems. He made the analogy of using the Prob Method to prove non-prob results. This reminded me of the following false counterarguments I've heard about new techniques:



The Prob Method: Isn't that just counting?

Kolg complexity: Isn't that just the Prob Method?

Information complexity: Isn't that just Kolg complexity?

Counting: Isn't that just Information Complexity?

In all of the cases above the complaint is idiotic--- while one COULD translate some (all?) proofs using Prob Method to Counting, it is easier to think in terms of Prob. The translation would be harder than just getting used to thinking probabilistically.

By coincidence I spend some of my time at CCC looking for simple examples of generating functions where it would be difficult to do it any other way. I found one and liked it so much that I did a write up FOR YOU MY READERS! I suspect that it COULD be done using just algebra (or something) but you wouldn't want to. Here is the theorem and a link to my write up:

(Schur's Theorem) Let a1,a2,...,aL be denominations of coins such that no number ≥ 2 divides all of them. Then, for large n, the number of ways to make change of n cents is

nL-1/((L-1)! a1 a2 ... aL) + O(nL-2)

For full proof see here. My writeup is based on that in Wilf's book generatingfunctionology (the title page really does use a small g for the first letter).





The above was my INTENDED POST. However, when I showed the Gen-function proof of Schur's theorem to some students, one of them, Sam (a HS student), came back the next day with a purely combinatorial proof. It was not completely rigorous but I am sure that he and most of my readers, could make it so without too much effort. While having two proofs (Gen-function and Combinatorial) is MORE enlightening for me and for my readers, it does dampen my point that this is a theorem for which the gen-function proof is easier. I COULD argue that the gen-function proof did not require as much cleverness, or that once you put in the rigor it is harder, but I don't really have confidence in those arguments. I include the combinatorial proof in the writeup pointed to above. Which proof is better? A matter of taste. However, I hope you enjoy both of them!