Results 1 to 8 of 8

Math Help - induction proof

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    76

    Unhappy induction proof

    I need some help with this induction proof.I'm like stuck at a crucial point and don't know how to get past it and complete the proof

    The question says:

    Suppose b1,b2,b3...
    is a sequence defined as follows :  b1= 4 , b2 = 12

    bk = bk-1  + bk-2  for all integers k>= 3
    prove that bn is divisible by 4 for all integers n>=1


    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by NidhiS View Post
    yea
    not much to do here.

    clearly it is true for n = 1, since b_1 = 4 which is divisible by 4

    assume it is true for n

    then b_{n + 1} = b_n + b_{n - 1}

    but b_n and b_{n - 1} are divisible by 4 by our inductive hypothesis, thus b_{n + 1} is divisible by 4, since it is the sum of two numbers divisible by 4

    the proof is complete

    of course you should clean up the proof, it is more of an outline. but i did more than half the work for you
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    76
    This is what I did:

    lets assume that p(k) is divisible by 4 (INDUCTIVE HYPOTHESIS)
    so p(k) : bk = bk-1 + bk-2

    we have to show that p(k+1) is divisible my 4.

    p(k+1) : bk+1 = bk + bk-2
    we know that bk is divisible my 4
    such that bk = 4l for some integer l

    then what next?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2008
    Posts
    76
    er thanks! that actually helped .Let me go back and flip through the pages and see which theorem cna be used to justify this proof.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by NidhiS View Post
    This is what I did:

    lets assume that p(k) is divisible by 4 (INDUCTIVE HYPOTHESIS)
    so p(k) : bk = bk-1 + bk-2

    we have to show that p(k+1) is divisible my 4.

    p(k+1) : bk+1 = bk + bk-1
    we know that bk is divisible my 4
    such that bk = 4l for some integer l

    then what next?
    by the hypothesis, it is true for every b_k for 1 \le k \le n, so the claim is true for b_{k - 1} as well, so b_{k - 1} = 4m for m \in \mathbb{Z}

    thus, b_{k + 1} = 4I + 4m = 4(I + m)...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2008
    Posts
    76
    well i think you over generalized the proof ,in a way.

    er what if k=1 then b 1 = 4l but b0 is not..
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2008
    Posts
    76
    I mean b0 is not divisible by 4
    Follow Math Help Forum on Facebook and Google+

  8. #8
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by NidhiS View Post
    I mean b0 is not divisible by 4
    b_0 doesn't exist, the first term of your sequence is b_1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum