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!

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

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook