Results 1 to 4 of 4

Math Help - recurrence relations

  1. #1
    Newbie
    Joined
    Oct 2007
    Posts
    17

    recurrence relations

    I am hoping that someone can check if I did the first relation correctly and then give me a clue as to how to attack the second one. Thank you for being willing to share your knowledge and time.

    a sub n = 2 n a sub n-1 a sub zero = 1

    a sub n = 2 n a sub n-1 + 2 n a sub n-2....2(n) (1)

    a sub n = 2^n

    The second problem is:

    Solve a sub n = a sub n-1 + 1 + 2^n-1

    I have no idea how to attack this and I am sorry I do not know how to enter subscripts!!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by frostking2 View Post
    I am hoping that someone can check if I did the first relation correctly and then give me a clue as to how to attack the second one. Thank you for being willing to share your knowledge and time.

    a sub n = 2 n a sub n-1 a sub zero = 1

    a sub n = 2 n a sub n-1 + 2 n a sub n-2....2(n) (1)

    a sub n = 2^n

    The second problem is:

    Solve a sub n = a sub n-1 + 1 + 2^n-1

    I have no idea how to attack this and I am sorry I do not know how to enter subscripts!!!!
    A_0 = 1
    A_n = 2n * A_{n-1}

    So do the first few:
    A_0 = (1)
    A_1 = (1)*2(1)
    A_2 = (1)*2(1)*2(2)
    A_3 = (1)*2(1)*2(2)*2(3)
    A_4 = (1)*2(1)*2(2)*2(3)*2(4)

    So we see that we can rewrite it like so:
    A_4 = (1)*2(1)*2(2)*2(3)*2(4) = (2*2*2*2)(4*3*2*1) = 2^44!

    So
    A_n = 2^nn!

    To prove it:
    A_1 = 2(1)A_0 = 2(1)(1) = 2
    A_1 = 2^11!=2
    So our formula is true for n=1

    (1)*2(1)*2(2)*2(3)*...*2(n) = 2^nn!

    The next iteration will be 2(n+1) so multiply both sides by this:
    (1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = 2^nn!2(n+1)
    (1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = (2*2^{n})[n!(n+1)]
    (1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = 2^{n+1}(n+1)! = A_{n+1}

    So by induction, it is true.

    ---------
    Quote Originally Posted by frostking2 View Post
    Solve a sub n = a sub n-1 + 1 + 2^n-1
    Does it give you an A_0 or A_1?

    Also, can you use parenthases? I'm interpreting this as A_n = A_{n-1}+1+2^{n-1} But I am not sure this is correct.
    Last edited by angel.white; February 10th 2008 at 11:28 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2007
    Posts
    17

    Clarification of problem

    Quote Originally Posted by angel.white View Post
    A_0 = 1
    A_n = 2n * A_{n-1}

    So do the first few:
    A_0 = (1)
    A_1 = (1)*2(1)
    A_2 = (1)*2(1)*2(2)
    A_3 = (1)*2(1)*2(2)*2(3)
    A_4 = (1)*2(1)*2(2)*2(3)*2(4)

    So we see that we can rewrite it like so:
    A_4 = (1)*2(1)*2(2)*2(3)*2(4) = (2*2*2*2)(4*3*2*1) = 2^44!

    So
    A_n = 2^nn!

    To prove it:
    [tex]A_1 = 2(1)A_0 = 2(1)(1) = 2
    A_1 = 2^11!=2
    So our formula is true for n=1

    (1)*2(1)*2(2)*2(3)*...*2(n) = 2^nn!

    The next iteration will be 2(n+1) so multiply both sides by this:
    (1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = 2^nn!2(n+1)
    (1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = (2*2^{n})[n!(n+1)]
    (1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = 2^{n+1}(n+1)! = A_{n+1}

    So by induction, it is true.

    ---------

    Does it give you an A_0 or A_1?

    Also, can you use parenthases? I'm interpreting this as A_n = A_{n-1}+1+2^{n-1} But I am not sure this is correct.
    You did by some miracle figure it out. a(0) = 0 in this problem sorry I forgot to write it down. The answer to your first one really helps me to understand the process for first order equations. Thanks so much for your patience
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by frostking2 View Post
    You did by some miracle figure it out. a(0) = 0 in this problem sorry I forgot to write it down. The answer to your first one really helps me to understand the process for first order equations. Thanks so much for your patience
    A_0 = 0
    A_n = A_{n-1}+1+2^{n-1}

    So do the first few to see the pattern:
    A_0 = 0
    A_1 = 0+1+2^0 = 1+1
    A_2 = (1+2^0)+1+2^1 = (1+1) + (1+2)
    A_3 = (1+2^0)+(1+2^1)+1+2^2 = (1+1) + (1+2) + (1+4)
    A_4 = (1+2^0)+(1+2^1)+(1+2^2) + 1 + 2^3 = (1+1) + (1+2) + (1+4) + (1 + 8)

    Now evaluate it a bit:
    A_4= (1+2^0)+(1+2^1)+(1+2^2) + 1 + 2^3
    = (1+1+1+1) + (2^0+2^1+2^2+2^3)
    = (1+1+1+1) + (1+2+4+8)
    It should be readily apparent that 1+1+1+1 = 4 which is n, if you don't see that, then realize that it is \sum_{i=1}^n 1 = n

    =n+(2^0+2^1+2^2+2^3)
    Now, lets look at our sums of this for A_1 through A_4, and compare them to various powers of two since there is a very obvious correllation between the two (which is why I kept the 2^0 through 2^4 instead of just showing their values)
    A_1 = 1 compare to 2^1=2
    A_2 = 3 compare to 2^2=4
    A_3 = 7 compare to 2^3=8
    A_4 = 15 compare to 2^4=16

    Notice that in each case, this portion of our value is one less than 2^n. So:
    n+(2^0+2^1+2^2+2^3) = n+2^n-1 = A_n

    ----------

    Now to prove it:
    Inductive Hypothesis:
    A_n = (1+2^0) + ( 1+2^1) + (1+2^2) + ... + (1+2^{n-1}) = n+2^n-1

    Basis step:
    Using A_n = A_{n-1} + 1 + 2^{n-1}
    A_1 = 0 1+2^{1-1} = 2

    Using A_n = n+2^n-1
    A_1 = 1+2^1 - 1 = 2

    Inductive Step:
    (1+2^0) + ( 1+2^1) + (1+2^2) + ... + (1+2^{n-1}) = n+2^n-1

    The next step in the sequence is to add (1+2^{n-1+1}) = (1+2^n) to both sides.
    (1+2^0) + ( 1+2^1) + (1+2^2) + ... + (1+2^{n-1}) + (1+2^n)= n+2^n-1+(1+2^n)

    = (n+1)+(2^n+2^n)-1
    = (n+1)+2^n(1+1)-1
    = (n+1)+2^n*2-1
    = (n+1)+2^{n+1}-1 = A_{n+1}

    So by induction, it is true taht A_n = n+2^n-1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 28th 2011, 02:50 PM
  2. Recurrence relations
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: February 24th 2011, 09:45 AM
  3. Recurrence relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 1st 2010, 06:59 AM
  4. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  5. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 9th 2008, 11:06 AM

Search Tags


/mathhelpforum @mathhelpforum