Prove: $\frac{n^5}5 + \frac{n^4}2 + \frac{n^3}3 - \frac n {30}$ is an integer for $n \ge 0$ I am attempting to prove the following problem: 

Prove that $\frac{n^5}5 + \frac{n^4}2 + \frac{n^3}3 - \frac n {30}$ is an integer for all integers $n = 0,1,2,...$

I attempted to solve it by induction, but when proving for $n= x+1$ the algebra gets very messy very fast. I was wondering if this is the only way or if there is a quicker way to prove this. I guess I am a little unsure as to how to prove something is an integer. 
I also noticed that letting $f(x) = \frac{x^5}5 + \frac{x^4}2 + \frac{x^3}3 - \frac x{30}$ and deriving $f(x)$ yields a fairly clean result, but I don't know if this helps me at all. Any help would be great.
 A: I'm reluctant to add to the noise here, but the following is a systematic (trick-free) way to deal with this type of question: the set of integer valued polynomials  has $\mathbb{Z}$-basis given by the binomial coefficients $$f_k(x)=\left( \begin{matrix} x \\ k \end{matrix} \right)=\frac{x(x-1)(x-2) \cdots (x-k+1)}{k!}.$$ 
Now given an arbitrary polynomial $f(x)$, there is a unique expression 
$$f(x)=\sum a_k f_k(x)$$ as a linear combination of these $f_k(x)$'s, with coefficients $a_k$ that one can get quickly and recursively using the upper-triangularity of the change of basis from $x^k$ to $f_k(x)$. Then $f$ is integer valued iff $a_k \in \mathbb{Z}$ for all $k$. 
Edit: I was going to leave this out but can't resist. Let $\Delta$ be the operator $(\Delta f)(x)=f(x)-f(x-1)$, so that $\Delta(f)$ is a discrete version of the derivative of $f$. Then the coefficients above are given by the following discrete analog of Maclaurin's theorem:
$$a_k=(\Delta^k f)(0).$$ As pointed out by lhf below, to prove that the $a_k$'s are integers it's enough to check that the values $f(m)$ are integers for $\mathrm{deg}(f)+1$ consecutive integers $m$. 
A: First write over a common denominator:
$$\frac{n^5}5 + \frac{n^4}2 + \frac{n^3}3 - \frac n{30} = \frac{1}{30}(6n^5+15n^4+10n^3-n)$$
Thus we want to show that 30 always divides expression in parenthesis. Since $\gcd(5,6)=1$, it suffices to prove divisibility by 5 and 6 individually. My first attempt was to factor this polynomial (using a computer, as I'm lazy):
$$6n^5+15n^4+10n^3-n=n(n+1)(2n+1)(3n(n+1)-1).$$
Observe that $6\sum_{k=1}^n k^2=n(n+1)(2n+1)$. Hence the expression is divisible by 6. You can check that 5 does not divide the remaining factor $3n(n+1)-1$, so we need a different approach.
Instead, we reduce the original expression mod 5, that is,
$$6n^5+15n^4+10n^3-n \equiv n^5-n \;\text{mod}\;5.$$
The computer tells me that the expression on the right appears to be divisible by 5. Can you prove this by induction (or even easier Fermat's little theorem)?
A: Induction is the way to go, but I'd rather show the following fact:
$\frac{n^5}5 + \frac{n^4}2 + \frac{n^3}3 - \frac n {30}$ being an integer is the same as $a_n=6n^5+15n^4+10n^3-n$ being divisible by 30 for all $n\geq 0$. The base case is trivial. Assume that the statement is true for $n$, that is, $6n^5+15n^4+10n^3-n$ is divisible by $30$. Now, we can show that $a_{n+1}-a_n$ is also divisible by $30$ and we will be done. 
$$a_{n+1}-a_n = 6((n+1)^5-n^5)+15((n+1)^4-n^4)+10((n+1)^3-n^3)-((n+1)-n)$$
$$=6(5n^4+10n^3+10n^2+5n+1)+15(4n^3+6n^2+4n+1)+10(3n^2+3n+1)-1$$
$$=30n^4+120n^3+180n^2+120n+30$$
A: A trick I learnt from Bill Dubuque.
Write it as
$$\frac{n^5 - n}{5} + \frac{n^4 - n}{2} + \frac{n^3 - n}{3} + n$$
(See Bill's answer here: Using congruences, show $\frac{1}{5}n^5 + \frac{1}{3}n^3 + \frac{7}{15}n$ is integer for every $n$)
A: One quick way is to recognize that $$\frac{n^5}{5} + \frac{n^4}{2} + \frac{n^3}{3} - \frac{n}{30}$$ is nothing but $1^4 + 2^4 +\cdots + n^4$.
Another way is to look at $6n^5 + 15n^4 + 10n^3 - n$ and prove that $30$ divides it i.e. prove that $2$, $3$ and $5$ divide $6n^5 + 15n^4 + 10n^3 - n$.
A: Nobody's given the boring but direct brute-force answer.
Several have noted that you want to show that $30$ divides $6 n^5 + 15 n^4 + 10 n^3 - n$, for all $n$. In other words, that
$$ 6 n^5 + 15 n^4 + 10 n^3 - n \equiv 0 \pmod {30}$$
There are only 30 possible values of $n$ modulo 30. Just plug them in and see that you get 0 in every case.
(Optional) By factoring 30 into prime powers, we see that to prove it for modulo 30 is the same thing as jointly proving it for modulo 2, 3, and 5. Brute force is easier with these smaller moduli.
A: Joe, since your original question was to prove that it is an integer:
An extension of Sivaram Ambikasaran's answer:
First claim that 
$\frac{n^5}{5} + \frac{n^4}{2} + \frac{n^3}{3} - \frac{n}{30} = 1^4 + 2^4 +\cdots + n^4$
And show your claim by induction. (This should be straightforward)
Once your claim is proven, the given expression $\frac{n^5}{5} + \frac{n^4}{2} + \frac{n^3}{3} - \frac{n}{30} $ is the sum $1^4 + 2^4 +\cdots + n^4$ for every $n$, which means it is an integer.  Because $1^4 + 2^4 +\cdots + n^4$ for every $n$ is an integer.
