12
$\begingroup$

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.

7 Answers 7

27

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

  • 0
    Ah, that's a very helpful little trick. Thanks.2012-03-01
14

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

  • 0
    @JoeGrotheer: What I meant was that if you consider the summation $\sum_{m=1}^{n} m^k$ the leading order terms are $\frac{n^{k+1}}{k+1} + \frac{n^k}{2} + \mathcal{O}(n^{k-1})$. In your case, the leading order terms were $\frac{n^5}{5} + \frac{n^4}{2} + \mathcal{O}(n^3)$. Hence, with $k=4$, the guess would be to sum $n^4$.2012-03-01
11

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.

  • 6
    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.2012-03-02
8

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

  • 0
    You're right, it's slightly easier.2012-03-01
3

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

3

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$

1

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.

  • 0
    @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)2012-03-02