1. Not finding help here? Sign up for a free 30min 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!

Induction: 3^(2n) - 1 is an integral multiple of 8

  1. Sep 2, 2007 #1
    1. The problem statement, all variables and given/known data
    Prove by induction that,
    3^(2n) - 1 is an integral multiple of 8
    for all positive n >= 1.


    2. Relevant equations
    3^(2n) - 1


    3. The attempt at a solution

    First I plugged in some values for n..

    Some values I plugged in
    (1) 3^2(1) - 1 = 8
    (2) 3^2(2) - 1 = 80
    (3) 3^2(3) - 1 = 728
    (4) 3^2(4) - 1 = 6560
    (5) 3^2(5) - 1 = 59048

    These answers are all divisible by 8.
    3^(2n) - 1 = 8x ?? Would that be correct?
    3^(2n+1) - 1 = ???? How do I show this next step?
    I don't have an example of a multiple variable induction problem so I am not really sure how it's supposed to work.
     
  2. jcsd
  3. Sep 2, 2007 #2
    I don't see multiple variables. Use the normal method of solving a problem by induction.
     
  4. Sep 2, 2007 #3
    To prove something by induction, for some statement P(n) where n is some positive integer, you must simply do the following:

    1/ Show that it is true for k=1, that is P(k) is true.

    2/ Show that for each k>=1 that P(k+1) is true.

    For the first part, you have already done this:

    3^2*1 -1 = 8 -> it is divisible by 8.

    Now just do the second part !

    HINT : You can change this notation to 3^2n = 1 mod 8 to make life a little easier....
     
  5. Sep 2, 2007 #4
    Hmm, mod 8? We never covered that in class so I wasn't sure of the notation.

    So I have 3^2n = 1 mod 8 as my P(n) statement and now I need to show that the statement is also true for 3^2(n+1) = 1 mod 8.
    So I multiply both side by two three's (or 9) to get the + 1 portion of the exponent...

    3*3[3^2(n)] = 3*3[1 mod 8]
    Which expands out to..
    3^2n+2 = 3*3[1 mod 8]
    3^2(n+1) = 3*3[1 mod 8]

    I don't think my teacher would enjoy the mod notation. lol
     
  6. Sep 2, 2007 #5
    Go back to the usual notation...

    Start with [tex]3^{2(n+1)} - 1[/tex]
     
  7. Sep 2, 2007 #6
    oof....

    3^2n = 1 mod 8 means that the remainder of 3^2n when divided by 8 is 1. It is another way of saying that 3^2n - 1 is a multiple of 8 (3^2n - 1 = 0 mod 8).

    3^2(n+1) = 3^(2n+2) = (3^2n)*(3^2) = (3^2n)*(9) = (3^2n)*1 mod 8

    But since you haven't done modulus arithmetic, you probably won't understand how to use this - the main argument being that 3^2n and 3^2(n+1) have the same remainder mod 8.

    Just do step 2 using the notation that you are familiar with, as neutrino has said.
     
  8. Sep 2, 2007 #7

    dextercioby

    User Avatar
    Science Advisor
    Homework Helper

    Forget the mod. Think induction. P(n)---->P(n+1). If 8/9^n -1 , then 9^n -1 =8k for some k in N. Then you need to show that 8/9^(n+1) -1 . Which means that 8/9 * 9^n -1 or 8/(8+1)* 9^n -1 . Can you take it from here ?
     
  9. Sep 2, 2007 #8
    Okay so..

    [tex]3^{2n}-1 = something*8[/tex]
    [tex]3^{2n}-1 = 8(k)[/tex]
    [tex]\frac{3^{2n}-1}{8} = k[/tex]

    We want to show that
    [tex]\frac{3^{2(n+1)+1}-1}{8} = multiple.of.8[/tex]


    [tex]9(\frac{3^{2n}-1}{8}) = 9(k)[/tex]
    [tex]\frac{3^{(2n+2)}-9}{8} = 9k[/tex]
    [tex]\frac{(3^{2n})(3^{2})-9}{8} = 9k[/tex]
    [tex]\frac{(3^{2n})(9)-9}{8} = 9k[/tex]

    Am I headed in the right direction?
     
    Last edited: Sep 2, 2007
  10. Sep 2, 2007 #9

    rock.freak667

    User Avatar
    Homework Helper

    Yep, you are about 2 or 3 lines away from showing that is always a multiple of 8

    HINT:[tex]3^{2n}-1=8k[/tex]
    try finding an expression for [tex]3^{2n}[/tex]
     
  11. Sep 2, 2007 #10
    [tex]\frac{(3^{2n})(9)-9}{8} = 9k[/tex]

    so from this..

    [tex]8(\frac{(3^{2n})(9)-9}{8}) = 8(9k)[/tex]
    [tex]3^{2n}(9)-9} = 72k[/tex]
    [tex]3^{2n}(9)} = 72k+9[/tex]
    [tex]3^{2n}(9) = 9(8k+1)[/tex]
    [tex]3^{2n}(9) = 3^{2n}(9)[/tex]
    [tex]1 = 1???[/tex]

    I'm lost. lol
     
  12. Sep 2, 2007 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Where did that first line come from?

    We know, by assumption that 3^2n -1 is an integer multiple of 8, now, we need to take 3^2(n+1) -1 and some how write it in terms of 3^2n-1 and some other terms, so do it - this is the only thing in induction as I've told you before - relate the n+1st statement to the n'th statement.
     
  13. Sep 3, 2007 #12
    Well, that's what I was trying to do. I don't see how your advice helps.
     
  14. Sep 3, 2007 #13
    [tex]3^{2(n+1)} - 1= 9.3^{2n} - 1 = ...[/tex]

    Is there a way you can factor out that 9?

    (It is assumed that [itex]3^{2n} - 1[/itex] is a multiple of eight.)
     
  15. Sep 3, 2007 #14
    Where did the 9.3 come from? or was it supposed to be [tex]9(3^{2n})[/tex]

    The only ways I see to factor that is either by factoring it leaving you with
    [tex]9(3^{2n} - 1/9) [/tex]

    or, by adding the - 1 to the other side.. ?

    I think you're suggesting I substitute the [tex]3^{2n} - 1[/tex] for some expression that is a multiple of 8, but I have no idea what that would be.

    9(8k) = ?
     
  16. Sep 3, 2007 #15
    Yes, 9 times 3 raised to 2n.

    Or you could rewrite the 1 and 9 - 8. [or the -1 as (-9 + 8), if you prefer.]
     
  17. Sep 3, 2007 #16

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Neutrino simply factored a 9 out of [tex]3^{2(n+1)}[/tex], like this: [tex]3^{2(n+1)} = 3^{2n+2} 3^2\cdot3^{2n}= 9\cdot3^{2n}[/tex]. You simply have to show that if [tex]3^{2n}-1= k_n\cdot8[/tex] then [tex]3^{2(n+1)}-1=k_{n+1}\cdot8[/tex]. Using the expansion, this becomes [tex]9\cdot3^{2n}-1=k_{n+1}\cdot8[/tex]. Can you proceed from here?
     
  18. Sep 4, 2007 #17
    Yea I see what you mean. This may be a dumb question but how is [tex]k_{n}[/tex] ever going to become [tex]k_{n+1}[/tex] since we don't know what k is?
     
  19. Sep 4, 2007 #18

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Ok. Time for an even bigger hint. Induction always starts by assuming the induction relation is true for some value of [itex]n[/itex], in this case, that

    [tex]3^{2n}-1 = k_n\cdot 8[/tex]

    which is obviously true for [itex]n=1[/itex] with [itex]k_1=1[/itex].
    Next step: Expand the relationship for [itex]n+1[/itex]:

    [tex]3^{2(n+1)}-1 = k_{n+1}\cdot 8[/tex]

    expanding the exponential term, this becomes

    [tex]9\cdot3^{2n}-1 = k_{n+1}\cdot 8[/tex]

    You already know that [itex]3^{2n}-1 = k_n\cdot 8[/itex] or [itex]3^{2n} = 1+k_n\cdot 8[/itex] Insert this in the above expansion.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Induction: 3^(2n) - 1 is an integral multiple of 8
Loading...