Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
Hint: this is true if and only if $n^3 - n$ is divisible by $6$. – Qiaochu Yuan Aug 15 '11 at 15:12
up vote 5 down vote accepted

$$\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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.