# Thread: Closed form for recurrence function

1. ## 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.

2. ## 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

3. ## Re: Closed form for recurrence function

Thanks for your fast, thorough, and helpful response and the thorough walk-through.
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 $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,