Results 1 to 5 of 5

Math Help - recurrence and algorithm

  1. #1
    Newbie
    Joined
    Apr 2007
    Posts
    8

    recurrence and algorithm

    Discrete maths
    I have three questions which I have spent time trying to do since the begining of this week but not sure whether I am at the right track.
    Would appreciated if you could help me. It has drive me crazy.
    I have typed and attached the questions as attachment as I cannot type maths super or sub script on this email.

    Help, it is driving me crazy!

    Thanks

    Fortuna
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,824
    Thanks
    713
    Hello, fortuna!

    Here's #3 . . .


    3. Solve the recurrence relation: .an .= .10an-1 - 25an-2, .a0 = 2, a1 = 15.

    Hint: If the characteristic equation factors to (t - r),
    . . . . then the general solution is: .a
    n .= .br^n + cnr^n
    The characteristic equation is: .t^n .= .10t^{n-1} - 25t^{n-2}

    . . Divide by t^
    {n-2}: . t .= .10t - 25 . . . . t - 10t + 25 .= .0

    . . Hence: .(t - 5) .= .0

    Then the general solution is: .a
    n .= .b5^n + cn5^n


    Since a
    0 = 2, we have: .b5^0 + c05^0 .= .2 . . . . b = 2

    Since a
    1 = 15 and b = 2, we have: .25 + c15 .= .15 . . . . c = 1


    Therefore, the general solution is: .a
    n .= .25^n + n5^n

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    procedure SortBits(S,i,j) {

    .. if (i==j)
    .... return ..............
    .. if (s(i) == 1){
    .... swap(s(i), s(j))
    .... SortBits(S,i,j-1)
    .... }
    .. else {
    .... SortBits(S,i+1,j)
    .. }
    }

    (a) If the length of the unsorted part of the sequence is 1 j=i+1 in the call
    SortBits(S, i, j). So one of the lines SortBits(S,i,j-1), or SortBits(S,i+1,j)
    is executed both of which do nothing and return, so b1 = 1.

    (b) Entering the with j=i+n, SortBits is called with an unsorted length
    of n-1, so:

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

    (c) I'm not sure what solution method you are expected to use, but
    the solution is b_n = n.

    (d) b_{25} = 25.

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2007
    Posts
    8

    Question one - Any chance of a solution

    Captain Black

    Is is possible still to get the workings and solution to question one.

    Thanks.

    Fortuna
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fortuna View Post
    Captain Black

    Is is possible still to get the workings and solution to question one.

    Thanks.

    Fortuna
    Unfortunatly I don't understand what the question is asking.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  2. recurrence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 8th 2009, 03:46 PM
  3. recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 1st 2009, 10:53 PM
  4. Finding the recurrence from an algorithm
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 22nd 2008, 06:32 PM
  5. recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 7th 2008, 09:35 AM

Search Tags


/mathhelpforum @mathhelpforum