# Divisibility using binomial coefficients

I have to prove that $6 \mid n^3 + 5n$ in a number of ways. One that I've been finding impossible is binomial coefficients. This is the problem statment:

Use an expression in terms of binomial coefficients to prove $n^3 + 5n$ is divisible by $6$.

-
Hint: this is true if and only if $n^3 - n$ is divisible by $6$. –  Qiaochu Yuan Aug 15 '11 at 15:12

$$\rm\displaystyle\ \ n^3+5\:n\ =\ n^3-n + 6\:n\ =\ (n+1)\:n\:(n-1) + 6\:n\ =\ 6\ {n+1\choose 3} + 6\ {n\choose 1}$$

In fact it is a classical result of Polya and Ostrowski (1920) that any integer valued polynomial, i.e. any $\rm\:f(x)\in \mathbb Q[x]\:$ with $\rm\:f(\mathbb Z)\subset \mathbb Z\:,\:$ is an integral linear combination of binomial coefficients, see for example Polya And Szego, Problems and theorems in analysis, vol II, Problem 85 p. 129 and its solution on p. 320. These results have been extended to much more general rings (e.g. Dedekind domains) by Cahen at al.

-
It is easy to verify that $x^n = \sum_{k=0}^n \binom{x}{k} k! S^{(2)}_{n,k}$, where $S^{(2)}_{n,k}$ are Stirling numbers of the second kind, so it follows for $f(x) \in \mathbb{Z}[x]$. Which book should I look at for proof for $\mathbb{Q}[x]$ ? Thanks –  Sasha Aug 15 '11 at 17:09
@Sasha See the newly added links in my answer. –  Bill Dubuque Aug 15 '11 at 17:38

It so happens that $n^3+5n = 6 \left( \binom{n}{3} + \binom{n}{2} + \binom{n}{1} \right)$.

Your result follows because binomial coefficients are integers.

-