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

Homework Help: Induction seems to not work?

  1. Jun 11, 2008 #1


    User Avatar
    Homework Helper

    1. The problem statement, all variables and given/known data

    Prove by mathematical induction,or otherwise,that [itex]23^{2n}+31^{2n}+46[/itex] is divisible by 48 for all [itex]n \geq 0[/itex]

    2. Relevant equations

    3. The attempt at a solution

    Assume true for n=N


    [tex] \times (23^2 + 31^2)[/tex]

    [tex]23^{2N+2}+31^{2N+2}+46(23^2 + 31^2)+23^2(31^{2N})+31^2(23^{2N})=48A(23^2 + 31^2)[/tex]

    [tex]23^{2N+2}+31^{2N+2}+68540+31^{2N}(528+1)+23^{2N}(960+1)=48A(23^2 + 31^2)[/tex]

    Simplifying gives me what I need, i.e. things divible by 48, but 68540 is not...any suggestions?
  2. jcsd
  3. Jun 11, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    Everything is not supposed to be divisible by 48. You can drop the things that are, of course. Now you just want to show 68540+31^(2N)+23^(2N) gives a remainder of 46 when divided by 48. BTW, it's easier without induction. Just observe 23^2 and 31^2 are both equal to 1 mod 48.
  4. Jun 11, 2008 #3
    Code (Text):

    what's this doing there? if this is a part of the first equation ...

    at n+1:
    23^(2n)*23^2 + 31^(2n)*31^2+46

    now trying writing this in orginal form:

    23^(2n)*528 + 23^(2n) + 31^(2n)*31^2+46

    do same for 31 ..
  5. Jun 11, 2008 #4
    since you already got the answer.. here's what I did:

    23^(2n)*528 + 23^(2n) + 31^(2n)*960 + 31 ^(2n) +46

    = {23^(2n) + 31 ^(2n) +46} + {23^(2n)*528 + 31^(2n)*960}

    everything divisible by 48
  6. Jun 11, 2008 #5


    User Avatar
    Homework Helper

    Well I multiplied what I assumed to be true by [itex]23^2+31^2[/itex] so could get [itex]23^{2N+2}+31^{2N+2}[/itex]

    wouldn't I need to show that everything is divisible by 48 for it to be true,hence why I can't show 68540 is divisible by 48.

    I don't get how I am supposed to show it gives a remaineder of 48, when in the inductive hypothesis, I assumed that everything was together was divisible by 48.

    Also,I don't understand what 1 mod 48 means. If it has to do with modular arithmetic,then I definately don't know what you are talking about since I never learnt that.
  7. Jun 11, 2008 #6

    Over there, from induction you assumed that {23^(2n) + 31 ^(2n) +46} is divisible by 48

    at n+1 .. you get {23^(2n) + 31 ^(2n) +46} + {23^(2n)*528 + 31^(2n)*960}

    divide this by 48..
    {23^(2n) + 31 ^(2n) +46} is divisible
    23^(2n)*528 is divisible
    31^(2n)*960 is divisible...

    so everything is proved
  8. Jun 11, 2008 #7


    User Avatar
    Homework Helper

    So I am supposed to just substitute n=N+1 instead of building the (N+1)th term?
  9. Jun 11, 2008 #8
    yep, isn't this is what you do for induction?

    first assume it is true for n
    and then substitute n by n+1 .. and prove it is true
  10. Jun 11, 2008 #9


    User Avatar
    Science Advisor
    Homework Helper

    You really already have it, you just don't seem to see it. According to your inductive hypothesis, if you divide 23^(2N)+31^(2N) by 48, what is the remainder? Now look at the N+1 case. Assuming the hypothesis what's the remainder of 23^(2N+2)+31^(2N+2) divided by 48?
  11. Jun 12, 2008 #10


    User Avatar
    Science Advisor

    He didn't say "remainder of 48", he said remainder of 46- so that added to the other remainders, they add up to 48.

    232= 529= 11(48)+ 1, 312= 961= 20(48)+ 1
    So each has a remainder of one when divided by 48.

    Also (x+ 1)n= a string of things times powers of x + 1 and so has a remainder of 1 when divided by x. Both 232n and 312n have a remainder of 1 when divided by 48 for any n.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook