Today in class, a student asked a question that stumped me. I haven’t yet given myself a lot of time to think about it, but I went into the city after school for something and on the subway ride home I had my audiobook on and I basically didn’t “hear” anything because my mind kept wandering back to this problem. (Ack! Now I have to rewind like 30 minutes of it.) And so I wanted to share it with you in case you wanted to work on it. Feel free to throw your thoughts in the comments.
We’re studying combinatorics (the art of counting) in precalculus. And we were seeing things like
pop up as answers to counting questions. And each of these evaluates to an integer.
The student asked: “BUT WHY? Why do these happen to evaluate to an integer?”
To give credit to what we’ve been doing in class, we spent about 3-4 days building up a deep conceptual understanding of why these would be the answers to particular counting scenarios, starting with first principles [1]. And we knew, since they were answers to counting problems, and that the number of outcomes to our given scenarios had to be an integer, that these had to evaluate to an integer. I would argue we have formally proved using a conceptual argument they had to turn out to be an integer. I think this is quite elegant! So on a mathematical level, we’re done. We’ve proved it.
However I liked this question a lot because I remember having it myself when I was in high school. And when I was teaching combinatorics for the first time. And randomly every so often since. I absolutely am certain I have thought about this before, and I also am certain I have no memory if I ever answered the question for myself or not. (My mind is like a goldfish.
So I pose it to y’all. On a purely algebraic level, how can we prove the following will be an integer:
Or I’d be okay with an even simpler version: how could we prove (again, purely algebraically, or with number theory, but with no reference to combinatorics) that the following will be an integer:
It’s harder than it looks, at least for me upon initial glance. I mean, I’m me, and needed to ground myself, so I started with a concrete example:
And I did the “canceling” and I saw we have some stuff that happens to divide evenly…
Yay, we see the 6 in the numerator divides out with the 3 and 2 (or the 6 divides out the 3… and 8 divides out the 2). But it feels like happenstance. And the more I wrote up examples, and I saw random things divide out from the denominator into various numbers in the numerator without rhyme or reason, the more happenstansical it all felt. It didn’t leave me to the next step in a proof…
The more examples I did in this very concrete and simplistic way, the more magical it felt. That I could find the right numbers in the numerator to cancel out with the numbers in the denominator — and still be left with an integer at the end! I loved the feeling of magic in math, because it means there’s something that is happening that I don’t understand, that’s ripe to be mined! And the moment I make something magical into something “obvious,” that’s when I know I’ve fully understood something. Right now, I’m in the magical phase.
In any case, I was thinking maybe I need to move forward with a proof by contradiction… or even induction?
I’m not sure if any of this made sense. But if it did, I’d love any thoughts in the comments!
[1] I have a very unique way of introducing combinatorics. At some point I should blog about it! But it basically reduces many, many combinatorial problems to the same type of problem. By the end of our unit, students don’t see “combinations” and “permutations” as different things that are related to each other. We zoom out and end up seeing them as the same thing. And moreso, my approach even lets them solve more complicated problems that combinations and permutations can become a bit more challenging to use. :)
Continuous Everywhere but Differentiable Nowhere 
Oh I have encountered the same question before. If you want to use number theory only, try thinking in terms of prime exponent (v_p). The Legendre’s formula gives you the prime exponent of the factorials and it’s not difficult to see why v_p((a+b)!) >= v_p(a!)+v_p(b!) from there.
Here’s my thought. If you are doing (a+b)!/(a!b!), as you’ve already said, that will reduce to (a+b)P(a)/ b!. So, (a+b)P(b) will have b numbers in it. So, like, suppose b is 5. Every 5th number is a multiple of 5, so a group of 5 sequential numbers will have a multiple of 5, and so we can cancel that out. You’ll also, by that same logic, have a multiple of 4, a multiple of 3, and 2 multiples of 2.
It is possible to prove it by induction.
Prove it for n=1 and k=0, and n=1 and k=1.
Supose n!/((n-k)!k!) is integer for every k (0<=k<=n), and it will be easy demonstrated for (n+1)!/((n+1-k)!k!) using the known property
Cn,m=C(n-1,m-1)+C(n-1,m)