I remember vaguely getting into proofs of such things in number theory in college. I do not remember it as a very pretty thing. Actually I just looked for one, check out the proofs for Bertrand's Ballot Theorem:
http://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem But I think at this level, it is more a question of deriving the formula in the way you approached it. From a simple case, out to the generalized. Like once he sees the 5x4x3x2x1 pattern and you can tell him there is short hand for it (5!) is pretty cool. Then you can find a probability reference somewhere that gives the formalized formula and he can see if it matches.
