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: Prove that 4^(n+1) + 5 is divisible by 3

  1. Oct 13, 2008 #1
    Prove that 4^(n+1) + 5 is divisible by 3 for all non-negative integers n.

    Here's what I did:
    The Base Case, when n=0
    4^(0+1) + 5 = 4 + 5 = 9 --> divisible by 3

    Assume that 4^(k+1) + 5 is also divisible by 3 for all n=0,1,2,...k.
    Then it must also be true for k+1 and
    4^(k+1+1) + 5 = 4 x 4^(k+1) + 5

    My solution doesn't seem to be complete. Is there something wrong or missing?
     
  2. jcsd
  3. Oct 13, 2008 #2

    HallsofIvy

    User Avatar
    Science Advisor

    Re: Proofs

    Well, yes, it is surely not obvious, yet, that your last formula is divisible by 3: which is the whole point.

    How about writing 4 x 4^(k+1) as 3 x 4^(k+1)+ [4^(k+1)] so that 4 x 4^(k+1)+ 5 is equal to 3 x 4^(k+1)+ [4^(k+1)+ 5]? Can you see now that both terms are divisible by 3?
     
    Last edited by a moderator: Oct 14, 2008
  4. Oct 13, 2008 #3
    Re: Proofs

    Thank you =) I see it now.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook