Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction problem

  1. Sep 26, 2004 #1
    Use mathematical induction to prove for all natural numbers [tex]n[/tex].

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

    Say [tex] S = \{ n\in N:P(x)\} [/tex]

    Then [tex] 1\in S. [/tex] (1/3 + 1/5 + 7/15 = 15/15)

    So assume for some [tex] k\in N, k\in S [/tex]

    So, obviously I have to show [tex] (k+1)\in S [/tex].

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

    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
  2. jcsd
  3. Sep 26, 2004 #2
    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?
  4. Sep 26, 2004 #3
    Ah nevermind I got it. I messed up the first time. Heh, distributing is tedious.
  5. Sep 26, 2004 #4
    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.
  6. Sep 26, 2004 #5
    Heh, too bad I don't konw Fermat's "little theorem", although I have been meaning to study it. Thanks though.
  7. Sep 27, 2004 #6
    (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
    Last edited: Sep 27, 2004
  8. Sep 27, 2004 #7
    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.
  9. Sep 27, 2004 #8

    Yea, after reading your post, that's exactly what I did.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook