# 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 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$)

-
+1. nice ...... – user17762 Mar 1 '12 at 19:19
+1 Good memory! – Bill Dubuque Mar 1 '12 at 19:21
Isn't $\frac{n^5 - n}{5} + \frac{n^4 - n}{2} + \frac{n^3 - n}{3} = \frac{n^5}{5} + \frac{n^4}{2} + \frac{n^3}{3} -\frac{31n}{30}$ – Kirthi Raman Mar 1 '12 at 19:49
@KirthiRaman: There is a $+n$ term too. – Aryabhata Mar 1 '12 at 19:51
Oh, you just changed +1 to +n, thats good! – Kirthi Raman Mar 1 '12 at 19:58

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

-
+1: How did you figure that out? – Aryabhata Mar 1 '12 at 19:30
@Aryabhata If one attempts an inductive proof then one would compute the first difference, yielding $\rm\:f(n)-f(n-1) = n^4,\:$ hence $\rm\:f = \sum n^4$ – Bill Dubuque Mar 1 '12 at 19:46
@BillDubuque: Probably, but I am guessing Sivaram has some other trick up his sleeve :-) – Aryabhata Mar 1 '12 at 19:48
@Aryabhata: When I saw the first coefficient was $\frac15$ and the second coefficient was $\frac12$, I guessed it should be $\sum n^4$ and checked it to be true. (since $\sum n^k$ has the leading coefficient as $\frac1{k+1}$ and the second coefficient is always $\frac12$ independent of $k$.) – user17762 Mar 1 '12 at 19:51
@SivaramAmbikasaran: Thanks! – Aryabhata Mar 1 '12 at 19:53

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.

-
Perhaps because it is not really quicker (without involving computers) than an inductive proof? +1 though. – Aryabhata Mar 1 '12 at 19:58
@Aryabhata More importantly, brute-force checks don't work for symbolic exponents, as does, e.g. $$\rm \frac{n^p}p + \frac{n^q}q -\frac{(p+q)n}{pq}\ =\ \frac{n^p-n}p + \frac{n^q-n}q$$ – Bill Dubuque Mar 1 '12 at 20:08
@BillDubuque: Agreed. – Aryabhata Mar 1 '12 at 20:09
IMO, people vastly undervalue this sort of proof and problem solving technique, even leading some students to not even understand that "reduce the problem down to a small number of possibilities, then check them" is a viable approach to a problem. Even when slicker approaches are available, I still think the dumb, "obvious" approaches like this should be pointed out, particularly when it wasn't obvious to the student. – Hurkyl Mar 2 '12 at 18:36

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

-
This is indeed a good idea but how does it apply concretely to the question as asked? – lhf Mar 1 '12 at 20:32
Well, compute the coefficients $a_k$ for the polynomial $f$ above. Then if they are integers, you have proved that $f$ is integer-valued (as I wrote above, this condition characterizes integer-valued polynomials). – Stephen Mar 1 '12 at 21:12
Since $f$ has degree 5, you only need to compute its value at 6 consecutive integers. If these values are all integers, then all values of $f$ at integers are integers. There is no need to compute the coefficients because they are repeated differences of those values. – lhf Mar 1 '12 at 21:52
@lhf, Because of discrete Taylor, computing the values of $f$ at six consecutive integers is basically the same thing as computing the coefficients $a_k$. Perhaps this is what you are getting at? – Stephen Mar 1 '12 at 22:00
yes. But my point is that computing the values of $f$ at six consecutive integers is easier than computing the coefficients. No big deal, though. – lhf Mar 1 '12 at 22:11

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

-

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)?

-

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.

-
That's precisely what Sivaram meant! – Bill Dubuque Mar 1 '12 at 20:25
@Bill Dubuque, For clarity purposes proofs have to be legible (I mentioned in my answer it is an extension to Sivaram's answer, not claiming this is a different answer) – Kirthi Raman Mar 2 '12 at 13:01