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!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Mathenatucak Induction Problems in discrete math
  1. Discrete math problems (Replies: 6)

Loading...