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: Need help with a proof by induction, please

  1. Sep 4, 2008 #1
    Using proof by induction, prove that (3^(2n-1))+1 is divisible by 4

    so this is what i could do so far:

    for n=1
    3^(2*1-1)+1=4 which is divisible by 4
    assume truth for n=k
    (3^(2k-1))+1 is divisible by 4
    and i know that next i have to prove for n=k+1 but i really have no idea what to do witht that.
    please help
     
  2. jcsd
  3. Sep 4, 2008 #2
    If you substitute n = k + 1, you get

    [tex]
    3^{2(k+1) - 1} + 1 = 3^{2k-1} 3^2 + 1
    [/tex]

    By assumption, [tex] 4 | 3^{2k-1} + 1 [/tex] so try to re-write [tex] 3^{2k-1} 3^2 + 1 [/tex] in a form that has a factor of [tex] 3^{2k-1} + 1 [/tex].
     
  4. Sep 4, 2008 #3

    statdad

    User Avatar
    Homework Helper

    The general term is

    [tex]
    a_n = 3^{2n-1}+1
    [/tex]

    and you've shown that $a_1$ is divisible by four, and you've assumed the same for $a_k$ for some $k \ge 1$.

    Look at [tex] a_{k+1} [/tex].

    [tex]
    3^{2(k+1)-1} +1 = 3^{2k+2-1} + 1 = 3^{2k -1} 3^2 + 1
    [/tex]

    The goal is to show that this is also divisible by four - the fact that [tex] a_k [/tex] is divisible by four will play a role in this.
     
    Last edited by a moderator: Sep 4, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook