# Closed form for recurrence function

• Sep 29th 2011, 04:28 PM
Closed form for recurrence function
I'm trying to figure out how many of the $\displaystyle x^L$ strings from an alphabet of $\displaystyle x$ characters, say $\displaystyle \left\{{a, b, c, d}\right\}$, do NOT contain a particular substring $\displaystyle s$ which itself contains no overlapping substrings. I figure that a decent recurrence relation is $\displaystyle S_L=4\times S_{L-1}-3\times S_{L-4}$ where $\displaystyle S_n$ is the number of $\displaystyle L$ length strings with no substring $\displaystyle s$ and:
$\displaystyle 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.

• Sep 29th 2011, 06:01 PM
MonroeYoder
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 $\displaystyle a_n = 4a_{n-1}-3a_{n-4}$

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

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

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

The left side of our equation is $\displaystyle \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 $\displaystyle 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 $\displaystyle -3x^4(a_0+a_1x+a_2x^2+\ldots)=-3x^4G(x)$

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

$\displaystyle 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)$

$\displaystyle 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$

$\displaystyle 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$

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

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

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

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

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

Thus the coefficient of $\displaystyle x^n$ is $\displaystyle \frac{255}{256}$
And now that I've done all this, I realize that induction clearly shows that every $\displaystyle 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
• Sep 30th 2011, 12:59 PM
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 $\displaystyle S_{n}=n^{4}$ for $\displaystyle n \in \{1,2,3\}, S_{4}=255$ and $\displaystyle S_{5} = 1008$.
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,