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

  • 8
    +1 Good memory!2012-03-01
  • 0
    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}$2012-03-01
  • 0
    @KirthiRaman: There is a $+n$ term too.2012-03-01
  • 0
    Oh, you just changed +1 to +n, thats good!2012-03-01
  • 0
    @KirthiRaman: I did that 21 minutes ago :-) But yes, I had a +1 earlier which was a typo. You have a sharp eye :-)2012-03-01
  • 0
    No biggy, I am an old person with a lot of time2012-03-01
  • 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
    +1: How did you figure that out?2012-03-01
  • 0
    @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$2012-03-01
  • 0
    @BillDubuque: Probably, but I am guessing Sivaram has some other trick up his sleeve :-)2012-03-01
  • 3
    @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$.)2012-03-01
  • 0
    @SivaramAmbikasaran: Thanks!2012-03-01
  • 0
    Once you have identified remarkably that $\frac{n^5}{5} + \frac{n^4}{2} + \frac{n^3}{3} - \frac{n}{30}$ is indeed $1^4 + 2^4 +\cdots + n^4$, there is nothing to prove. Because that sum is an integer for every $n$.2012-03-01
  • 0
    @Kirthi Yes, of course it is clear that sums of fourth powers are integers, that's why Sivaram mentioned that rep. If you think that deserves explicit emphasis, then it would have been better to simply add a comment to Sivaram's answer, rather than to add a duplicate answer, since that may confuse some folks.2012-03-01
  • 0
    @Sivaram Can you explain what you wrote in the parentheses regarding the first two coefficients of summation n^k? I'm not sure I fully understand that point. Otherwise beautifully done. Your alternative answer was a solution I quickly realized after I posted the question, but your first answer is simple and eloquent--the ideal for proofs. Thanks a lot.2012-03-01
  • 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.

  • 1
    Perhaps because it is not really quicker (without involving computers) than an inductive proof? +1 though.2012-03-01
  • 1
    @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 $$2012-03-01
  • 0
    @BillDubuque: Agreed.2012-03-01
  • 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
    This is indeed a good idea but how does it apply concretely to the question as asked?2012-03-01
  • 0
    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).2012-03-01
  • 1
    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.2012-03-01
  • 0
    @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?2012-03-01
  • 0
    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.2012-03-01
  • 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.

  • 1
    That's precisely what Sivaram meant!2012-03-01
  • 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