Answer:
Apply induction on (for integers ) after showing that is divisible by for .
Step-by-step explanation:
Lemma: is divisible by for .
Proof: assume that for some , is not divisible by .
The combination is known to be an integer. Rewrite the factorial to obtain:
.
Note that (a prime number) is in the numerator of this expression for . Since all terms in this fraction are integers, the only way for to be non-divisible by is for the denominator of this expression to be an integer multiple of .
However, since , the prime number would not a factor of . Similarly, since , the prime number would not be a factor of , either. Thus, would not be an integer multiple of the prime number . Contradiction.
Proof of the original statement:
Base case: . Indeed is divisible by .
Induction step: assume that for some integer , is divisible by . Need to show that is also divisible by .
Fact (derived from the binomial theorem ):
.
Rewrite using this fact:
.
For this particular , is divisible by by the induction hypothesis.
is also divisible by since is an integer and (by lemma) each of the coefficients is divisible by .
Therefore, , which is equal to , is divisible by .
In other words, for any integer , if is divisible by , then would also be divisible by .
Therefore, is divisible by for all integers .