There is a genre of undergraduate polynomial divisibility problems which look like this: Show that f(n) is divisible by some integer k.
These problems often appear to be (elementary) number theory problems. However, often there is a rather elegant proof associated with them which is based on combinatorics.
The crux of this proof is that the polynomial counts the number of equivalence classes of a certain kind.
jmount ·19 hours ago
Show replies
agnishom ·3 hours ago
There is a genre of undergraduate polynomial divisibility problems which look like this: Show that f(n) is divisible by some integer k.
These problems often appear to be (elementary) number theory problems. However, often there is a rather elegant proof associated with them which is based on combinatorics.
The crux of this proof is that the polynomial counts the number of equivalence classes of a certain kind.
This is closely related to https://en.wikipedia.org/wiki/Burnside%27s_lemma
The question at the end of the post is whether _all_ such problems must come this way
t43562 ·3 hours ago
np_tedious ·12 hours ago
Exercise left to the reader:
Prove 7*n^3 + n is divisible by 2
Show replies
dang ·16 hours ago
Show replies