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

$$ n^3/3 + n^5/5 + 7n/15 $$

is an integer for every integer n >= 1.

I define P(n) to be: $$ n^3/3 + n^5/5 + 7n/15 $$ is an integer.

For my basis step, P(1) is true because $$ 1^3/3 + 1^5/5 + 7(1)/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, $$ k^3/3 + k^5/5 + 7k/15 $$ is an integer.

So based on that assumption, I need to now show that P(k+1) is true, i.e., that $$ (k+1)^3/3 + (k+1)^5/5 + 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:

$$ k^3/3 + k^5/5 + 7k/15 = 15m $$ for some integer m. Then I solve for m: $$ (k^3/3 + k^5/5 + 7k/15)/15 = 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:

$$ (5(k+1)^3 + 3(k+1)^5 + 7(k+1)) / 15 $$

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
add comment

3 Answers

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
add comment

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
add comment

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
add comment

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.