2
$\begingroup$

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

  • 1
    Hint: this is true if and only if $n^3 - n$ is divisible by $6$.2011-08-15

2 Answers 2

5

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

  • 0
    @Sasha See the newly added links in my answer.2011-08-15
4

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.