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: Mathenatucak Induction Problems in discrete math

  1. Mar 2, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove that 3 divides n3 + 2n whenever n is a positive integer.

    2. Relevant equations



    3. The attempt at a solution

    Basis Step :
    P(1) : [13 + 2(1) ] /3
    [1+2] /3
    [3]/3
    1
    Since 3/3 =1, P(1) is true

    Inductive Step:
    [ k3 + 2k ] /3 = [(k +1)3 + 2(k+1) ] /3

    [k(k2 + 2k)] /3 = [(k)3 + (3k)2 + 5k +3] /3


    1. The problem statement, all variables and given/known data

    Prove that f1 2 + f2 2 +...+ fn 2 when n is a positive integer.

    2. Relevant equations
    The Fibonacci numbers f0, f1, f2..., are defined by the equations f0 = 0, f1 = 1 and fn = fn-1 + fn-2 for n = 2,3,4...



    3. The attempt at a solution

    Basic Step:
    P(1) : f1 2 = f1 * f2

    12 = (1)*(1)
    1= 1
    Since f1 2 = f1 * f2 , P(1) is true.

    Inductive Step:
    fk 2 = fk * fk+1

    fk 2 + fk+1 2
    = f1+fk+1 + (fk+1)
     
    Last edited: Mar 2, 2010
  2. jcsd
  3. Mar 2, 2010 #2

    Mark44

    Staff: Mentor

    For the first problem, I'm having some trouble understanding what you're doing.
    You have established the base case, P(1). IOW, when n = 1, n^3 + 2n = 1 + 2 = 3, so the proposition is true for n = 1.

    Assume that the proposition is true when n = k. IOW, assume that k^3 + 2k is divisible by 3. Another way to say this is that k^3 + 2k = 3m for some integer m.

    Now, when n = k + 1, you want to show/prove that (k + 1)^3 + 2(k + 1) is divisible by 3. You do NOT want to show that k^3 + 2k = (k + 1)^3 + 2(k + 1), which is essentially what you wrote in your post.

    To show that (k + 1)^3 + 2(k + 1) is divisible by 3, expand the two terms. You will need to use the assumption that k^3 + 2k = 3m.
     
  4. Mar 2, 2010 #3
    I'm lost about showing that (k + 1)^3 + 2(k + 1) is divisible by 3. I expanded the right side of the equation [k^3 + 2k)] /3 = [(k)^3 + (3k)^2 + 5k +3] /3. So, do I replace on the left side [k(k^2 + 2k)] /3 with 3m??
     
    Last edited: Mar 2, 2010
  5. Mar 2, 2010 #4

    Mark44

    Staff: Mentor

    This equation is bogus - [k^3 + 2k)] /3 = [(k)^3 + (3k)^2 + 5k +3] /3 - get rid of it, and also get rid of those /3 things that you have.

    Take another look at what I said at the end of my previous post.
     
  6. Mar 3, 2010 #5
    Ok, what about the second problem??
     
  7. Mar 4, 2010 #6

    Mark44

    Staff: Mentor

    What is the second problem?
    There's nothing there to prove. You have to have a statement of some kind in order to prove it.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook