Results 1 to 3 of 3

Math Help - Closed form for recurrence function

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    2

    Closed form for recurrence function

    I'm trying to figure out how many of the x^L strings from an alphabet of x characters, say \left\{{a, b, c, d}\right\}, do NOT contain a particular substring s which itself contains no overlapping substrings. I figure that a decent recurrence relation is S_L=4\times S_{L-1}-3\times S_{L-4} where S_n is the number of L length strings with no substring s and:
    S_1=S_2=S_3=S_4 and S_5 = \frac{255}{256}.
    This is function-able but it would be great to have this as a closed form equation. Thanks in advance for any ideas.

    Addie
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Sep 2011
    Posts
    58

    Re: Closed form for recurrence function

    Not sure I understand your problem exactly, but I'll try to give you a closed form equation for the recursive relation a_n = 4a_{n-1}-3a_{n-4}

    So we can get a_n\cdot x^n = 4a_{n-1}\cdot x^n -3a_{n-4}\cdot x^n

    Taking sums of all sides we get \sum_{n=4} a_nx^n = \sum_{n=4}4a_{n-1}x^n - \sum_{n=4}3a_{n-4}x^n

    Let G(x) = \sum_{n=0}a_nx^n

    The left side of our equation is \sum_{n=4} a_nx^n=a_4x^4+a_5x^5+\ldots = G(x)-a_0-a_1x-a_2x^2-a_3x^3

    The first term on the right is 4x(a_3x^3+a_4x^4+\ldots)=4x(G(x)-a_0-a_1x-a_2x^2)

    The second term on the right is -3x^4(a_0+a_1x+a_2x^2+\ldots)=-3x^4G(x)

    So since you said that a_1=a_2=a_3=a_4=a_5=\frac{255}{256} we have

    G(x)-\frac{255}{256}(1+x+x^2+x^3)=4x(G(x)-\frac{255}{256}-\frac{255}{256}x-\frac{255}{256}x^2)-3x^4G(x)

    G(x)+3x^4G(x)=\frac{255}{256}(1+x+x^2+x^3)+4xG(x)-\frac{255}{64}x-\frac{255}{64}x^2-\frac{255}{64}x^3

    G(x)+3x^4G(x)-4xG(x)=\frac{255}{256}(1+x+x^2+x^3)-\frac{255}{64}x-\frac{255}{64}x^2-\frac{255}{64}x^3

    G(x)(1-4x+3x^4) = -\frac{765}{256}(x+x^2+x^3)+\frac{255}{256}

    G(x) = \frac{-765(x+x^2+x^3)+255}{256(1-4x+3x^4)}

    According to wolframalpha.com the right side becomes \frac{255}{256(1-x)}

    So G(x)=\frac{255}{256}\frac{1}{1-x}

    And by power series representations we have that G(x)=\frac{255}{256}\sum_{n=0}x^n

    Thus the coefficient of x^n is \frac{255}{256}
    And now that I've done all this, I realize that induction clearly shows that every a_n=\frac{255}{256} *note after re-reading the problem you may not have given the first 4 values of the sequence, which makes this wrong

    Eh well... at least I got to review working with generating functions. You can change one of your initial values or many of them and repeat this analysis so maybe it will be helpful
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2011
    Posts
    2

    Re: Closed form for recurrence function

    Thanks for your fast, thorough, and helpful response and the thorough walk-through.
    Quote Originally Posted by MonroeYoder View Post
    Not sure I understand your problem exactly, but I'll try to give you a closed form equation for the recursive relation
    Sorry if I made that unclear. The problem is related to something I'm trying to do in my lab and I was trying to keep the molecular bio lingo out so that I wouldn't be flamed for not posting to a biology forum. Basically you got it right. Unfortunately, you were also right that I messed up the initial values. I think I should have written those as S_{n}=n^{4} for n \in \{1,2,3\}, S_{4}=255 and S_{5} = 1008.
    Eh well... at least I got to review working with generating functions. You can change one of your initial values or many of them and repeat this analysis so maybe it will be helpful
    I'm sure it will. I've been hoping to learn about generating functions for a while now; I'll use your reply as a tutorial.
    Thanks,
    Addie
    Does anyone have any suggestions for a good tutorial on generating functions?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 12th 2011, 07:58 PM
  2. closed form for sequence z=z^2+c & generating function
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 4th 2011, 04:05 AM
  3. Closed-form solution of a recurrence relation.
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 4th 2011, 03:06 PM
  4. closed integral form for gamma function
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 19th 2010, 03:42 AM
  5. Linear recurrence sequence, closed form.
    Posted in the Algebra Forum
    Replies: 6
    Last Post: February 21st 2009, 08:20 AM

Search Tags


/mathhelpforum @mathhelpforum