Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

7 Answers 7

up vote 25 down vote accepted

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

share|improve this answer
    
+1. nice ...... –  user17762 Mar 1 '12 at 19:19
8  
+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$.

share|improve this answer
    
+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
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$.) –  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.

share|improve this answer
1  
Perhaps because it is not really quicker (without involving computers) than an inductive proof? +1 though. –  Aryabhata Mar 1 '12 at 19:58
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 $$ –  Bill Dubuque Mar 1 '12 at 20:08
    
@BillDubuque: Agreed. –  Aryabhata Mar 1 '12 at 20:09
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. –  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$.

share|improve this answer
    
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). –  S123 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? –  S123 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$$

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.