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: Another Proof via Induction

  1. Dec 2, 2005 #1
    The problem asks that I compute [tex]3^n-2^n[/tex] for positive integer values of n, starting at 1 and working through a handful of consecutive integers.
    From there I am to make a general observation about the values and then attempt to prove it with induction.

    So I found the values:
    n=1, 3^1-2^1 = 1
    n=2, 3^2-2^2 = 5
    n=3, 3^3-2^3 = 19
    n=4, 3^4-2^4 = 65
    n=5, 3^5-2^5 = 211
    n=6, 3^6-2^6 = 665
    n=7, 3^7-2^7 = 2059
    n=8, 3^8-2^8 = 6305
    n=9, 3^9-2^9 = 19171

    From this I made the observation that for even values of n, [tex]3^n-2^n[/tex] is divisible by 5.
    So I worked with the idea that [tex]3^{2n}-2^{2n}[/tex] is divisible by 5 for ALL positive integers.

    Using mathematical induction:

    For n=1
    [tex]3^{2(1)}-2^{2(1)} = 5[/tex]

    For k
    [tex]3^{2k}-2^{2k}[/tex]

    For k+1
    [tex]3^{2(k+1)}-2^{2(k+1)}[/tex]
    [tex]= 3^{2(k+1)}-2^{2(k+1)} -3^{2k} +3^{2k} -2^{2k} +2^{2k}[/tex]
    [tex]= 3^{2k}(3^2-1) - 2^{2k}(2^2-1) + (3^{2k} -2^{2k})[/tex]
    The 3rd term is case k, assumed to be divisible by 5

    Working with the remaining terms:
    [tex]3^{2k}(8) - 2^{2k}(3)[/tex]
    [tex]= 3^{2k}(8) - 2^{2k}(3) + 2^{2k}(5) - 2^{2k}(5)[/tex]
    [tex]= 3^{2k}(8) - 2^{2k}(8) + 2^{2k}(5)[/tex]
    [tex]= 8(3^{2k} - 2^{2k}) + 5(2^{2k})[/tex]
    The first term has case k as a factor, and the second term has 5 as a factor, making both divisible by 5

    Thus [tex]3^{2n}-2^{2n}[/tex] is divisible by 5 for all positive integers


    Does this look valid?
    Any way to clean it up?

    Thanks in advance for your time!
    GM
     
    Last edited: Dec 2, 2005
  2. jcsd
  3. Dec 2, 2005 #2

    HallsofIvy

    User Avatar
    Science Advisor

    What you've done is valid but somewhat more complicated than is necessary. Notice that 32(k+1)= 32k+2= 9(32k) and that 22(k+1)= 22k+2= 4(22k). And, of course, 9- 4= 5.
     
  4. Dec 2, 2005 #3
    So:
    9(32k) - 4(22k)
    5(32k) + 4(32k) - 4(22k)
    5(32k) + 4(32k - 22k), both divisible by 5
    Yeah, that is much simpler.
    I seem to have a gift for missing the obvious and making more work for myself. :tongue:
    Thanks again!
    GM
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook