Results 1 to 4 of 4

Math Help - prove that recurrence relation is odd

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    130

    prove that recurrence relation is odd

    Hello!

    I just want to be sure if I did solve the task correctly.

    The task is:

    Prove that bn is odd for integers n>=1

    b_1=1
    b_2=3
    b_k=b_{k-2}+2b_{k-1} for k>=3

    The attempt at a solution

    Induction basis:

    b_1=1 true 1 is odd
    b_2=3 true 2 is odd

    Now the question is:

    Could I use the strong (complete) induction?

    If I can use it, the solution is simple:

    Let the recurrence relation is true for all k, such that n<k and n=k i.e n<=k
    b_k=b_{k-2}+2b_{k-1}

    then for n=k+1

    b_{k+1}=b_{k-1}+2b_{k}

    b_{k-1} is odd and 2b_k is even therefore odd+even=odd

    Is this correct?

    Thank you.

    Regards.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,418
    Thanks
    718

    Re: prove that recurrence relation is odd

    Quote Originally Posted by p0oint View Post
    Let the recurrence relation is true for all k, such that n<k and n=k i.e n<=k
    b_k=b_{k-2}+2b_{k-1}

    then for n=k+1

    b_{k+1}=b_{k-1}+2b_{k}

    b_{k-1} is odd and 2b_k is even therefore odd+even=odd
    You assume that the property you need to prove, i.e., that b_n or b_k is odd, and not the recurrence relation, holds for all previous n or k. Secondly, do you mean it is true for all n (instead of k) such that n <= k? Perhaps you could rewrite the induction step more carefully.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2009
    Posts
    130

    Re: prove that recurrence relation is odd

    Hello!

    Yeah I messed the things a little bit.

    I meant if P(1) is true and for every integer k>=1 P(1), P(2), ... , P(k) imply P(k+1) then P(n) is true for all n>=1

    Is this ok?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,418
    Thanks
    718

    Re: prove that recurrence relation is odd

    I meant if P(1) is true and for every integer k>=1 P(1), P(2), ... , P(k) imply P(k+1) then P(n) is true for all n>=1
    This is correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 3rd 2011, 07:21 AM
  2. Prove recurrence relation equals sum of permutations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 16th 2010, 09:00 AM
  3. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 23rd 2010, 12:06 PM
  4. Prove limit of recurrence relation
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 1st 2007, 12:57 PM
  5. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 22nd 2006, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum