Monday, June 22, 2015

Learning from teaching a HS student Schur's theorem on change

(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 nL-1 /(L-1)!a1a2...aL  + Θ(nL-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.

  1. 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.
  2. 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.
  3. 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!
  4. 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.
  5. 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.)
Moral of the story: By working with a HS student I was forced to find a proof for partial frac deomp, find a non-calc proof of a Taylor series, and obtain an interesting corollary. Hence this is already a win!

1 comment:

  1. For #5, you might want to look at

    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.