Closed form for recurrence function

**adlai** · September 29th 2011, 04:28 PM

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

**MonroeYoder** · September 29th 2011, 06:01 PM

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

**adlai** · September 30th 2011, 12:59 PM

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,
Addie
Does anyone have any suggestions for a good tutorial on generating functions?

Thread: Closed form for recurrence function

LinkBack

Thread Tools

Display

Closed form for recurrence function

Re: Closed form for recurrence function

Re: Closed form for recurrence function

Similar Math Help Forum Discussions

How to prove that a function has no closed-form integral?

closed form for sequence z=z^2+c & generating function

Closed-form solution of a recurrence relation.

closed integral form for gamma function

Linear recurrence sequence, closed form.

Search Tags