1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

    3^{2(k+1) - 1} + 1 = 3^{2k-1} 3^2 + 1

    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


    User Avatar
    Homework Helper

    The general term is

    a_n = 3^{2n-1}+1

    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].

    3^{2(k+1)-1} +1 = 3^{2k+2-1} + 1 = 3^{2k -1} 3^2 + 1

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Need help with a proof by induction, please