(All the math this post refers to is in my manuscript which is here.)

Recall Schur's theorem on making change as stated in wikipedia and other source:

*Let a1,...,aL be rel prime coin denominations. Then the number of ways to make n cents*

*change is n*

^{L-1}/(L-1)!a1a2...aL + Θ(n^{L-2}).The proof I knew (from Wilfs book on generating functions) was not difficult; however,it involved roots of unity, partial fractions, Taylor series, and Generating functions. I needed to present the proof to a HS students who was in precalc. The writeup above is what I finally came up with. A few points.

- HS students, or at least mine, knew complex numbers. Hence roots-of-unity was okay. The proof of Schur's theorem has another plus: he had asked me just recently how complex numbers could be used in the real world since they weren't... real. I said the are often used as an intermediary on the way to a real solution and gave him an example of a cubic equation where you spot a complex solution and use it to obtain the real solutions. Schur's theorem is a more sophisticated example of using complex numbers to get a result about reals (about naturals!) so that's a win.
- Partial Fractions. If the student had had calculus then he would know what partial fractions were and believe me when I said they always work. But since he had not had calculus I prepared a proof that they worked. Then I realized--- I have never seen a proof that they work! This is a matter of timing- I saw them in High School Calculus in 1975 which was taught without proofs (just as well, analysis is a bad first-proof course) and I didn't quite realize that the techniques they taught us aren't quite a proof that it works. I came up with my own proof (I can't imagine its original but I have not found a ref) in 2015. That's 40 years between seeing a concept and proving that it works. A personal record.
- Taylor Series. I needed the Taylor series for 1/(1-x)^b (just for b a natural). I came up with a proof that does not use calculus and that a HS student could follow. Very happy that I was forced to do do this. Actually uses a nice combinatorial identity!
- The lemmas about partial fractions and about Taylor series are of course very very old. Are my proofs new? I doubt it though I have not been able to find a reference. If you know one please leave a polite comment.
- Having gone through the proof so carefully I noticed something else the proof yields: Let M be the LCM of a1,...,aL. For all 0\le r\le M-1 there is a poly p of degree L-1 such that if n\equiv r mod M then p(n) is the number of ways to make change of n cents. I suspect this is known but could not find a ref (again- if you know one then please leave a polite comment.)

For #5, you might want to look at

ReplyDeletehttps://en.wikipedia.org/wiki/Ehrhart_polynomial#Ehrhart_Quasi-Polynomials

The polynomial property you state is another way of saying the number of ways to make change is the Ehrhart quasipolynomial of the polytope {a^Tx <= n} where a is the vector (a_1, a_2, .., a_L) of change denominations.