Closed form for recurrence function

I'm trying to figure out how many of the strings from an alphabet of characters, say , do NOT contain a particular substring which itself contains no overlapping substrings. I figure that a decent recurrence relation is where is the number of length strings with no substring and:

This is function-able but it would be great to have this as a closed form equation. Thanks in advance for any ideas.

Addie

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

So we can get

Taking sums of all sides we get

Let

The left side of our equation is

The first term on the right is

The second term on the right is

So since you said that we have

According to wolframalpha.com the right side becomes

So

And by power series representations we have that

Thus the coefficient of is

And now that I've done all this, I realize that induction clearly shows that every *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

Re: Closed form for recurrence function

Thanks for your fast, thorough, and helpful response and the thorough walk-through. Quote:

Originally Posted by

**MonroeYoder** 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 for and .

Quote:

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?