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 
):
![\begin{aligned} & (n + 1)^{7} \\ &= \sum\limits_{j = 0}^{7} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right] && (\ast)\\ &= \genfrac{(}{)}{0}{}{7}{0} \, n^{0} + \genfrac{(}{)}{0}{}{7}{7} \, n^{7} + \sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right] \\ &= 1 + n^{7} + \sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right]\end{aligned}](https://tex.z-dn.net/?f=%5Cbegin%7Baligned%7D%20%26%20%28n%20%2B%201%29%5E%7B7%7D%20%5C%5C%20%26%3D%20%5Csum%5Climits_%7Bj%20%3D%200%7D%5E%7B7%7D%20%5Cleft%5B%5Cgenfrac%7B%28%7D%7B%29%7D%7B0%7D%7B%7D%7B7%7D%7Bj%7D%5C%2C%20n%5E%7Bj%7D%5Cright%5D%20%26%26%20%28%5Cast%29%5C%5C%20%26%3D%20%5Cgenfrac%7B%28%7D%7B%29%7D%7B0%7D%7B%7D%7B7%7D%7B0%7D%20%5C%2C%20n%5E%7B0%7D%20%2B%20%5Cgenfrac%7B%28%7D%7B%29%7D%7B0%7D%7B%7D%7B7%7D%7B7%7D%20%5C%2C%20n%5E%7B7%7D%20%2B%20%5Csum%5Climits_%7Bj%20%3D%201%7D%5E%7B6%7D%20%5Cleft%5B%5Cgenfrac%7B%28%7D%7B%29%7D%7B0%7D%7B%7D%7B7%7D%7Bj%7D%5C%2C%20n%5E%7Bj%7D%5Cright%5D%20%5C%5C%20%26%3D%201%20%2B%20n%5E%7B7%7D%20%2B%20%5Csum%5Climits_%7Bj%20%3D%201%7D%5E%7B6%7D%20%5Cleft%5B%5Cgenfrac%7B%28%7D%7B%29%7D%7B0%7D%7B%7D%7B7%7D%7Bj%7D%5C%2C%20n%5E%7Bj%7D%5Cright%5D%5Cend%7Baligned%7D)
.
Rewrite using this fact:
![\begin{aligned} & 6\, (n + 1) + (n + 1)^{7} \\ =\; & 6\, (n + 1) + \left(1 + n^{7} + \sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right]\right) \\ =\; & 6\, n + n^{7} + 7 + \sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right]\right) \end{aligned}](https://tex.z-dn.net/?f=%5Cbegin%7Baligned%7D%20%26%206%5C%2C%20%28n%20%2B%201%29%20%2B%20%28n%20%2B%201%29%5E%7B7%7D%20%5C%5C%20%3D%5C%3B%20%26%206%5C%2C%20%28n%20%2B%201%29%20%2B%20%5Cleft%281%20%2B%20n%5E%7B7%7D%20%2B%20%5Csum%5Climits_%7Bj%20%3D%201%7D%5E%7B6%7D%20%5Cleft%5B%5Cgenfrac%7B%28%7D%7B%29%7D%7B0%7D%7B%7D%7B7%7D%7Bj%7D%5C%2C%20n%5E%7Bj%7D%5Cright%5D%5Cright%29%20%5C%5C%20%3D%5C%3B%20%26%206%5C%2C%20n%20%2B%20n%5E%7B7%7D%20%2B%207%20%2B%20%20%5Csum%5Climits_%7Bj%20%3D%201%7D%5E%7B6%7D%20%5Cleft%5B%5Cgenfrac%7B%28%7D%7B%29%7D%7B0%7D%7B%7D%7B7%7D%7Bj%7D%5C%2C%20n%5E%7Bj%7D%5Cright%5D%5Cright%29%20%5Cend%7Baligned%7D)
.
For this particular , is divisible by by the induction hypothesis.
![\sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right]](https://tex.z-dn.net/?f=%5Csum%5Climits_%7Bj%20%3D%201%7D%5E%7B6%7D%20%5Cleft%5B%5Cgenfrac%7B%28%7D%7B%29%7D%7B0%7D%7B%7D%7B7%7D%7Bj%7D%5C%2C%20n%5E%7Bj%7D%5Cright%5D)
is also divisible by since is an integer and (by lemma) each of the coefficients is divisible by .
Therefore, 
, which is equal to ![6\, n + n^{7} + 7 + \sum\limits_{j = 1}^{6} \left[\genfrac{(}{)}{0}{}{7}{j}\, n^{j}\right]\right)](https://tex.z-dn.net/?f=6%5C%2C%20n%20%2B%20n%5E%7B7%7D%20%2B%207%20%2B%20%20%5Csum%5Climits_%7Bj%20%3D%201%7D%5E%7B6%7D%20%5Cleft%5B%5Cgenfrac%7B%28%7D%7B%29%7D%7B0%7D%7B%7D%7B7%7D%7Bj%7D%5C%2C%20n%5E%7Bj%7D%5Cright%5D%5Cright%29)
, 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 .
