Proving Induction Problem: P(x) is an Integer for all Natural Numbers n

[Yoss]

Use mathematical induction to prove for all natural numbers $$n$$.

P(x) = $$\frac{n^3}{3} + \frac{n^5}{5} + \frac{7n}{15}$$ is an integer.

Say $$S = \{ n\in N:P(x)\}$$

Then $$1\in S.$$ (1/3 + 1/5 + 7/15 = 15/15)

So assume for some $$k\in N, k\in S$$

So, obviously I have to show $$(k+1)\in S$$.

I'm not sure how to start. In order for it to be an integer, then 15 must divide
$$5n^3 + 3n^5 + 7n$$.

I've worked through, by substituting (k + 1), tried distributing throughout, but I can't seem to get anywhere to factor out a multiple of 15. Can anyone give a suggestion of how to manipulate this so I can prove it? Thanks

 

[Yoss]

Also, what I'm trying to do, is after I substitute in (k+1), I'm trying to form the original equation, since that's divisible by 15, and with that part, I'm trying to get the other part to be divisible by 15. You think this is the way to go?

 

[Yoss]

Ah nevermind I got it. I messed up the first time. Heh, distributing is tedious.

 

[robert Ihnot]

Another way to do it is to look at congruences. Since x^n==x modulo n by Fermat's little theorem, we can easily show that 5n^3 + 3n^5 + 7n==0+3+7 ==0 Modulo 5, which is to say that 5 always divides this expression. And then can do the same thing for Modulo 3.

 

[Yoss]

Another way to do it is to look at congruences. Since x^n==x modulo n by Fermat's little theorem, we can easily show that 5n^3 + 3n^5 + 7n==0+3+7 ==0 Modulo 5, which is to say that 5 always divides this expression. And then can do the same thing for Modulo 3.

Heh, too bad I don't konw Fermat's "little theorem", although I have been meaning to study it. Thanks though.

 

[robert Ihnot]

Ah nevermind I got it. I messed up the first time. Heh, distributing is tedious.

(I thought you were saying that you had found the answer, that is why I thought it O.K. to suggest a second solution.)

Anyway, it can be done strictly by induction. First proving for 1 and assuming that 5k^3+3k^5+7K ==0 Modulo 15, or if you like, divisible by 15. If we use the binominal theorem, for the value of k+1, we have: 5(k^3+3k^2+3k+1) + 3(k^5 + 5k^4+10k^3+10k^2+5k+1) +7(k+1) to show divisible by 15. So we subtract out the original expression for k, which we assume equals 0. Then we get ride of all terms that are a multiple of 15, and all that is left is 5+3+7 = 15.

Fermat's Little Theorem: http://mathworld.wolfram.com/FermatsLittleTheorem.html

 

[Yoss]

(I thought you were saying that you had found the answer, that is why I thought it O.K. to suggest a second solution.)

Anyway, it can be done strictly by induction. First proving for 1 and assuming that 5k^3+3k^5+7K ==0 Modulo 15, or if you like, divisible by 15. If we use the binominal theorem, for the value of k+1, we have: 5(k^3+3k^2+3k+1) + 3(k^5 + 5k^4+10k^3+10k^2+5k+1) +7(k+1) to show divisible by 15. So we subtract out the original expression for k, which we assume equals 0. Then we get ride of all terms that are a multiple of 15, and all that is left is 5+3+7 = 15.

Fermat's Little Theorem: http://mathworld.wolfram.com/FermatsLittleTheorem.html

Nono, I did actually solve the problem. The first time I tried distributing all the polynomials I made an arithmetical error. But I tried it again and found the original equation divisible by 15 and then the remaining equation that came out of that was also divisible by 15.

 

[Yoss]

(I thought you were saying that you had found the answer, that is why I thought it O.K. to suggest a second solution.)

Anyway, it can be done strictly by induction. First proving for 1 and assuming that 5k^3+3k^5+7K ==0 Modulo 15, or if you like, divisible by 15. If we use the binominal theorem, for the value of k+1, we have: 5(k^3+3k^2+3k+1) + 3(k^5 + 5k^4+10k^3+10k^2+5k+1) +7(k+1) to show divisible by 15. So we subtract out the original expression for k, which we assume equals 0. Then we get ride of all terms that are a multiple of 15, and all that is left is 5+3+7 = 15.

Fermat's Little Theorem: http://mathworld.wolfram.com/FermatsLittleTheorem.html

Yea, after reading your post, that's exactly what I did.