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 want to prove that

$$\frac{n^3}{3}+\frac{n^5}{5}+\frac{7 n}{15}$$

is an integer for every integer $n \geq 1$.

I define P(n) to be:

$$\frac{n^3}{3}+\frac{n^5}{5}+\frac{7 n}{15}$$ is an integer.

For my basis step, P(1) is true because

$$\frac{1^3}{3}+\frac{1^5}{5}+\frac{7}{15}=1$$ which is an integer.

The inductive step is what's tripping me up...

Let k be an arbitrary positive integer. Assume that P(k) is true, that is,

$$\frac{k^3}{3}+\frac{k^5}{5}+\frac{7 k}{15}$$ is an integer.

So based on that assumption, I need to now show that P(k+1) is true, i.e., that

$$\frac{(k+1)^3}{3} +\frac{(k+1)^5}{5} +\frac{7 (k+1)}{15}$$ is an integer.

At this point, I am stuck as to where to go next...

I have tried rewriting the assumption:

$$\frac{k^3}{3}+\frac{k^5}{5}+\frac{7 k}{15}=15 m$$ for some integer m. Then I solve for m:

$$\frac{1}{15} \left(\frac{k^3}{3}+\frac{k^5}{5}+\frac{7 k}{15}\right)=m$$

But this looks like a dead-end, seems there's nothing I can do with this to the "to prove" equation.

I have also tried re-writing the "to show" equation as this, but I get a dead end there and am not sure where to go next:

$$\frac{1}{15} \left(5 (k+1)^3+3 (k+1)^5+7 (k+1)\right)$$

share|improve this question
1  
You want to prove $A(n)$ is an integer for every $n\geqslant1$ and you know $A(1)$ is. You could compute $A(n+1)-A(n)$ and show this is an integer for every $n\geqslant1$. –  Did Nov 3 '11 at 12:06

5 Answers 5

up vote 3 down vote accepted

Why do you think that $P(k) = 15m$ for some integer $m$ if it does not hold for, say $k=1$? If you assume that $P(k)$ is integer then the strategy is to show that $$ P(k+1) - P(k) \in\mathbb Z $$ and let us do it: $$ P(k+1) - P(k) = \frac{1}{5}((n+1)^5-n^5)+\frac13((n+1)^3 - n^3)+\frac7{15} = $$ $$ = \frac15(5n^4+10n^3+10n^2+5n+1) +\frac13(3n^2+3n+1)+\frac7{15} $$ $$ = n^4+2n^3+2n^2+n +\frac15+n^2+n+\frac13+\frac{7}{15} $$ $$ = n^4+2n^3+3n^2+2n+1 $$ $$ =(n^2+n+1)^2\in \mathbb Z $$ and you're done.

share|improve this answer
    
The last bit is written more neatly as $(n^2+n+1)^2$. –  J. M. Nov 3 '11 at 12:13
    
Thanks! Just what I needed –  mathemagician11 Nov 3 '11 at 12:19
2  
@JM: thanks, now it's even more pyramidal. –  Ilya Nov 3 '11 at 12:20

This problem becomes trivial when thought of in terms of division. Realize that the common denominator of the fractions is 15. Thus, all we need to show is that $$15 \mid 3n^5+5n^3+7n\;\;\forall n$$ Since $15=3 \cdot 5$, all we have to show is that both 3 and 5 will divide this for all $n$. To make this easy, we simply show the equation is 0 modulo 3 and modulo 5 for all $n$.

Note that mod 3, we are left with $2n^3+n$ and need only consider $n=0,1,2$. This checks out easily.

Similarly, mod 5, we are left with $3n^5+2n$ and must consider $n=0,1,2,3,4$. Again, this checks out.

Since $\gcd(3,5)=1$ it follows that this equation will be divisible by their product, 15, for all $n$ as well.

share|improve this answer
    
A general theorem tells us that $x^p=x$ in $\mathbb{Z}/p$ if $p$ is a prime. Therefore, $3n^5=3n$ in $\mathbb{Z}/5$, so $3n^3+2n=5n=0$ in $\mathbb{Z}/5$. Likewise, $2n^3+n=2n+n=3n=0$ in $\mathbb{Z}/3$. –  Baby Dragon Oct 11 '13 at 18:24

Here is a proof not by induction, but which may be instructive.

Using repeated differences on the first few values of $P(n)$ we get $$ \begin{array}{llll} 0 & 1 & 10 & 59 & 228 & 669 & 1630 & \\ 1 & 9 & 49 & 169 & 441 & 961 & \\ 8 & 40 & 120 & 272 & 520 & \\ 32 & 80 & 152 & 248 & \\ 48 & 72 & 96 & \\ 24 & 24 & \\ 0 & \\ \end{array} $$ Newton's interpolation formula then gives us $$ P(n)= 0 \binom{n}{0} + 1 \binom{n}{1} + 8 \binom{n}{2} + 32 \binom{n}{3} + 48 \binom{n}{4} + 24 \binom{n}{5} $$

This is clearly an integer for all $n\ge 0$.

In general, if a polynomial of degree $d$ and with rational coefficients takes integer values for $d+1$ consecutive integers, then it takes integers values for all integer arguments because all repeated differences are integers and so are the coefficients in Newton's interpolation formula.

share|improve this answer
    
See also Integer-valued polynomial. –  lhf Jul 11 at 14:15

Expand the binomials and group the resulting fractions such that you get integers.

In other words, you know that

$$(k + 1)^3 = k^3 + 3k^2 + 3k + 1$$

and

$$(k + 1)^5 = k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1$$

That should do the trick.

share|improve this answer

You are needed to use the fact that integer is another integer. Now put $k$ and consider the result true then go for $k-1$. From step in which you put $k$ you get an equation that give an $\frac{k^3}{3}+\frac{k^5}{5}+\frac{7k}{15}=p$ (an integer). Using it and fact stated in line $1$ solves the problem.

share|improve this answer
2  
You should try not to call a question "easy" when helping someone. It does little more squash flat that person's confidence. –  user1729 Jul 11 at 10:55
    
Yeah, this is just unkind, poorly formatted, and unhelpful. –  JHance Jul 11 at 13:47

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.