Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical Induction and proofs

  1. Feb 6, 2007 #1
    1. The problem statement, all variables and given/known data

    1. Prove that if n is an even positive integer, then n³-4n is always divisible by 48.

    2. Prove taht the square of an odd integer is always of the form 8k+1, where k is an integer.

    3. Observe that the last two digits of 7² are 49, the last two digits of 7³ are 43, thel ast two digits of 7^4 are 01, and the last two digits of 7^5 are 07. Prove that the last two digits of 7^201 are 07.


    2. Relevant equations
    Don't know if any are applicable.


    3. The attempt at a solution
    Basically the homework handed out today for my semester 2 discrete and geometry class in high school. I have no experience in proofs and the teacher assigned this without doing any examples :(

    I need help on my form and revision on how I attempt these proofs and basically what I can work on to make them look more convincing and professional.

    1. Let n = 48k, 48k+2, 48k+4
    n³-4n divisible by 48
    =(48k)³-4(48)
    =110592k³-192k
    =192k(576k²-1)
    Since 192 is divisible by 48, statement is true.
    Should I check with 48k+2, 48k+4 afteR?

    2. Since k is an odd integer, we can represent it as 2k+1
    (2k+1)² = 8k + 1
    4k²+4k+1 = 8k +1
    4k²+4k=8k
    4k(k+1)=8k
    8k is divisible by 4k so statement is true.

    3. This one i need help the most.

    I figured
    7^1 = 7
    7^2 = 49
    7^3 = 343
    7^4 = 2401

    and it rotates from 7,9,3,1 (last digit) every 4 numbers...so 7^5 would end with a 7.

    so 7^4n+1 would yield a number that ends with 7, 7^4n+2 would yield a number that ends with a 9, etc

    so if 7^201 ends with a 7
    7^4n+1 = 7^201, n must be an integer
    4n+1 = 201
    4n = 200
    n = 50

    Conversely for 7^202
    7^4n+1 = 7^202
    4n+1 = 202
    4n = 201
    n is not an integer so 7^202 does not end with a 7.

    Getting confused...it looks right sometimes but sometimes it doesn't...am I donig the right stuff?
     
  2. jcsd
  3. Feb 6, 2007 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I don't think you quite get mathematical induction. Take 1) and let f(n)=n^3-4*n. You want to prove this is divisible by 48 for n=2,4,6,8... You want to prove two things.

    i) f(2) is divisible by 48. (This is the easy part!)

    ii) IF f(n) is divisible by 48 THEN f(n+2) is divisible by 48.

    Do you see how those two things would prove the result for all positive even n?
     
  4. Feb 6, 2007 #3
    ah thank you i think i understand it a bit more now

    wait..is it f(n+2) or f(2n) ?
    i thought for any even number its 2n and for odd its 2n+1

    okay so

    f(2) = (2)³ - 4(2) = 0 therefore for n=2 it is true
    f(2n) = (2n)³ - 4(2n)
    = 8n³ - 8n
    = 8n(n²-1)

    how do i prove from hereforth that the expression is divisible by 48 for any value of n?
     
    Last edited: Feb 6, 2007
  5. Feb 6, 2007 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No! It is f(n+2). So once you have that it is true for f(2), then ii) tells you it is true for f(2+2)=f(4), which in turn means it's true for f(4+2)=f(6) etc etc.
     
  6. Feb 6, 2007 #5
    f(n+2) = (n+2)³ - 4(n+2)
    = n³+6n²+8n

    where do i go from here?
     
  7. Feb 6, 2007 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Well, we get to ASSUME f(n) is divisible by 48. How might we show this f(n+2) is also divisible by 48?
     
  8. Feb 6, 2007 #7
    factor........
     
  9. Feb 6, 2007 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I don't think it's going to work that way. Besides, we are TRYING to do induction here. That is what the assignment calls for.
     
  10. Feb 6, 2007 #9
    wait let me try this again
    f(n+2) = (n+2)³ - 4(n+2)
    = n³ + 6n² + 12n + 8 -4n - 8

    since f(n) = n³-4n and proven that it was divisible by 48

    f(n+2) = n³ - 4n + 6n² + 12n
    = n³ - 4n + 6n(n+2)
     
  11. Feb 6, 2007 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Good! So you've shown the difference between f(n+2) and f(n) is 6*n^2+12*n. Can you show that is divisible by 48? (Remember n is even, right?).
     
  12. Feb 6, 2007 #11
    6n² + 12n....
    so then n = 2k cause its even

    6(2k)² + 12(2k)
    6(4k²) + 24k
    24k² + 24k

    is that it?
     
  13. Feb 6, 2007 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I see that it is divisible by 24. Why is it divisible by 48?
     
  14. Feb 6, 2007 #13
    i dont know lol i'm so close....

    is it because since i tested f(2) beforehand, 2 is also divisible...

    and 2 x 24 = 48?
     
  15. Feb 6, 2007 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Your answer is 24*(k^2+k). Is k^2+k odd or even (where k can be either even or odd)?
     
  16. Feb 6, 2007 #15
    k²+k has to be even for any value of k.....so therefore its divisible by 2?
     
  17. Feb 6, 2007 #16

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes. So 24*(k^2+k) is divisible by what?
     
  18. Feb 6, 2007 #17
    is divisible by 48....

    so since both sides can be divisible by 48...can i conclude that f(n+2) is divisible by 48....and so conclude my whole proof altogether since i've proved both f(n) and f(n+2)
     
  19. Feb 6, 2007 #18

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    QED. It's a stepladder f(2)->f(4)->f(6)->f(8)... Write it up nicely, think about it and try the others in the same spirit.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Mathematical Induction and proofs
Loading...