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!

Induction, my first time; please be gentle.

  1. Sep 13, 2011 #1
    1. The problem statement, all variables and given/known data

    I like this thing call induction

    Prove that for every integer [tex]n\geq 0[/tex] that

    [tex]5| (9^n - 4^n)[/tex]


    3. The attempt at a solution

    1) Base Case n = 0

    [tex]9^0 - 4^0 = 0[/tex]

    Clearly it is true

    2) Take n = k + 1

    [tex]9^{k + 1} - 4^{k + 1} = 9^k 9 - 4^k 4 = 9^k (4 + 5) - 4^k 4 = 9^k 5 + 9^k 4 - 4^k 4 = 9^k 5 + 4(9^k - 4^k)[/tex]

    Now here is the problem. I know I did it correctly, but I don't know what to do with [tex]9^k 5 + 4(9^k - 4^k)[/tex] I know that 4 won't matter because I proved 1) and that 5 behind the 9^k would also disappear. But how do I formally say that?
     
  2. jcsd
  3. Sep 14, 2011 #2

    Mark44

    Staff: Mentor

    90 - 40 = 5
    You seem to be missing your induction hypothesis; i.e., that 5 | 9k - 4k. Another way to say this is that 9k - 4k = 5M for some integer M.
     
  4. Sep 14, 2011 #3
    ;;;
    No.
     
  5. Sep 14, 2011 #4

    Mark44

    Staff: Mentor

    Scratch that - you were right. I think it's getting late.

    Anyway, by the Induction Hypothesis, you know that 9k - 4k is divisible by 5, which means that 9k - 4k = 5M for some integer M.

    The rest of the proof hinges on showing that 9k + 1 - 4k + 1 can be related back to 9k - 4k in some way.

    9k + 1 - 4k + 1 = 9*9k - 4*4k
    = 4*9k - 4*4k + 5*9k

    Hopefully, you can do something with that.
     
  6. Sep 14, 2011 #5
    Even with 9k - 4k = 5M, I don't know what to do with

    4*(9k - 4k) + 5*9k
     
  7. Sep 14, 2011 #6

    Mark44

    Staff: Mentor

    4*(9k - 4k) + 5*9k = 4* 5M + 5*9k

    Can you show that this last expression is divisible by 5?
     
  8. Sep 14, 2011 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Your first term is divisible by 5 from the induction hypothesis. Your second term is divisible by 5 just by looking at it. So the sum is divisible by 5. Yes?
     
  9. Sep 14, 2011 #8
    Yeah but I don't know how to write it properly.
     
  10. Sep 14, 2011 #9

    Mark44

    Staff: Mentor

    Look at the expression on the right side of the equation in post #6. Factor 5 from each term.
     
  11. Sep 14, 2011 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    4*5*M+5*9^k=5*(4*M+9^k). That's 5 times an integer. I'm pretty sure anyone would believe that is divisible by 5. I'm not sure what you mean by 'write it properly'.
     
  12. Sep 15, 2011 #11
    1) Base Case n = 0

    [tex]S(n): 9^n - 4^n[/tex]

    [tex]9^0 - 4^0 = 0[/tex]

    Clearly it is true

    2) Assume that [tex]5|(9^n - 4^n)[/tex] is true, then we can show that S(n + 1) is also true, i.e.

    [tex]S(n + 1) = 9^{n + 1} - 4^{n + 1} = 5M[/tex] (1) [Would it better to write [tex]5| 9^{n + 1} - 4^{n + 1}[/tex] instead because it is confusing with what is below?]

    Assuming that S(n) is true, then [tex]\exists M \in \mathbb{Z}[/tex] such that

    [tex]9^n - 4^n = 5M[/tex]

    Thus

    [tex]9^{n + 1} - 4^{n + 1} = 9^n 9 - 4^n 4 = 9^n (4 + 5) - 4^n 4 = 9^n 5 + 9^n 4 - 4^n 4 = 9^n 5 + 4(9^n - 4^n) = 5M + 4^n + 4(5M) = 25M + 4^n[/tex]

    Since [tex]25M + 4^n \in \mathbb{Z}[/tex], it is clear that (1) is true by the Principles of Mathematical Induction.

    Q.E.D.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Induction, my first time; please be gentle.
Loading...