18  Putting Everything Together

We’ve done some examples where we take a description and create a finite state automaton. We’ve done state elimination to create regular expressions. So let’s look one last time at how to turn these regular expressions into formulae.

18.1 Trinary Example

In Section 17.3.4, we had the regular expression \[ 0^*[1(0 + 1)^*2 + 2(0 + 2)^*1](0 + 1 + 2)^*. \]

Now we could break this into sublanguages like \(L_0 = \{0\}\) and \(\Phi_{L_0} = x^{f(0)} = x^1\) but we can streamline this a bit.

  1. Take your regular expression.
  2. Replace each character like \(0, 1, 2\) with \(x^{f(0)}, x^{f(1)}, x^{f(2)}\). If we’re weighting by length these should all just be \(x\).
  3. Replace \(A^*\) by \(\frac{1}{1 - A}\).

Let’s illustrate: \[\begin{align*} &\phantom{{}={}}\; 0^*[1(0 + 1)^*2 + 2(0 + 2)^*1](0 + 1 + 2)^* \\ &\mapsto x^*[x(x + x)^*x + x(x + x)^*x](x + x + x)^* \\ &= x^*[2x^2(2x)^*](3x)^* \\ &= \frac{1}{1 - x}\frac{2x^2}{1 - 2x}\frac{1}{1 - 3x} \\ &= \frac{2x^2}{(1 - x)(1 - 2x)(1 - 3x)}. \end{align*}\]

18.1.1 Getting a formula

On it’s face, it’s hard to tell what the taylor series is for this function. So we first ask Sage to give us a partial fraction decomposition.

%display latex
A = 2x^2 / ((1 - x)*(1 - 2x)*(1 - 3x))
A.partial_fraction()
\(\displaystyle -\frac{1}{3 \, x - 1} + \frac{2}{2 \, x - 1} - \frac{1}{x - 1}\)

Sage typically puts the \(x\)’s first but it’s more useful to us to write this as \[ \frac{1}{1 - 3x} - \frac{2}{1 - 2x} + \frac{1}{1 - x}. \]

We use the important identity \(\frac{1}{1 - ax} = \sum a^n x^n\) to convert this to \[ \sum_{n = 0}^\infty 3^n x^n - 2 \sum_{n = 0}^{\infty} 2^n x^n + \sum_{n = 0}^\infty x^n = \sum_{n = 0}^\infty (3^n - 2 \cdot 2^n + 1) x^n. \]

Conclusion: there are \(3^n - 2 \cdot 2^n + 1\) trinary strings of length \(n\) with at least one \(1\) and one \(2\).

Note 18.1

We can also obtain this answer by Inclusion/Exclusion. Let \(X\) denote the set of all trinary strings of length \(n\). Let \(A\) be strings with no \(1\) and let \(B\) be strings with no \(2\). Then \(|X| = 3^n\) and \(|A| = |B| = 2^n\) since each represents strings with two choices of character.

We want \(|X| - |A \cup B| = |X| - |A| - |B| + |A \cap B|\) using the formula we had in Section 2.4. So \(3^n - 2^n - 2^n + 1\) which matches what we have using generating functions.

We’re beginning to see how generating functions tie together our material on binomial coefficients, strings, inclusion/exclusion and also recurrence relations.

18.2 Fibonacci Example

At the end of Section 17.4, we had the regular expression \((0 + 10)^*(\varepsilon + 1)\). We repeat our method to turn this into a generating function. First, we should point out that \(\varepsilon\) will become \(x^{f(\varepsilon)} = x^0 = 1\). So \[ (x + x^2)^*(1 + x) = \frac{1 + x}{1 - x - x^2}. \]

Partial fractions don’t help us out here. At least…not easily.

On the other hand, we know that the Fibonacci numbers satisfy the recurrence \(f_n = f_{n - 1} + f_{n - 2}\). To make the connection clearer, let us write this as

\[ f_n - f_{n - 1} - f_{n - 2}. \]

18.3 More Examples

Consider the sequence generated by \(a_0 = 0, a_1 = 0, a_2 = 1\) and \(a_n + 4a_{n - 1} - 2a_{n - 2} + 5a_{n - 3}\) for \(n \ge 3\).

We can compute a generating function \(\sum a_n x^n\) in Sage using the following commands.

Note

Per the Sage documentation, the coefficients are given in ascending order (from \(n - 3\) to \(n - 2\) to \(n - 1\)): \[ a_{n + 3} = -5 a_n + 2 a_{n + 1} - 4 a_{n + 2}. \]

C = CFiniteSequences(ZZ) # sequences over the integers
C.from_recurrence([-5, 2, -4], [0, 0, 1]).ogf()
\(\displaystyle \frac{x^{2}}{5x^{3} - 2x^{2} + 4x + 1}\)

The numerator is hard to predict as it depends on the initial values as well as the recurrence. But pay attention to that denominator: \[ 1 + 4x - 2x^2 + 5x^3 \]

These coefficients match our recurrence!

18.4 General Result

Suppose a Taylor series \(\sum a_n x^n\) can be written as a rational function \(P(x)/Q(x)\) where:

  1. \(\deg P < \deg Q\)
  2. \(Q(x) = c_0 + c_1x + c_2x^2 + \dots + c_kx^k\) (degree \(k\))

Then the coefficients \(a_n\) satisfy the recurrence relation

\[ c_0 a_n + c_1 a_{n - 1} + c_2 a_{n - 2} + \dots + c_k a_{n - k} = 0, \text{ for } n \ge k \]

(And the reverse holds as well!)

Note

The condition that \(\deg P < \deg Q\) isn’t crucial to this. It takes care of a few things. First, if \(\deg P \ge \deg Q\) we could do long division to simplify.

Second, if we have something like \(x/ (1 - x) = -1 + 1/(1 - x)\), then the recurrence relation we get from the denominator is \(a_n = a_{n - 1}\) but if we write down this Taylor series, the coefficients are \(0, 1, 1, 1, 1, \dots\). So the recurrence relation \(a_n = a_{n - 1}\) only holds if \(n \ge 2\).

The big takeaway here is: making \(\deg P \ge \deg Q\) alters the initial terms and the recurrence relation takes longer to kick in.

Proof. Let \(A = \sum a_n x^n = P(x) / Q(x)\). Multiplying both sides by \(Q(x)\) we should find that \(AQ = P\) (a polynomial). So \[\begin{align*} AQ &= (c_0 + c_1x + \dots + c_kx^k) \sum a_n x^n \\ &= c_0 \sum a_n x^n + c_1 \sum a_nx^{n + 1} + \dots + c_k \sum a_n x^{n + k} \\ &= c_0 \sum a_n x^n + c_1 \sum a_{n - 1}x^n + \dots + c_k \sum a_{n - k} x^n. \end{align*}\]

Now this is supposed to be a polynomial. And it is, if and only if the coefficients are \(0\) for \(n\) bigger than \(\deg P\) and in particular if \(n \ge k = \deg Q\). So for \(n \ge k\), we have \[ c_0 a_n + c_1 a_{n - 1} + \dots + c_k a_{n - k}. \]

And the steps here are reversible: if we satisfy this recurrence then \(AQ\) is a polynomial of degree less than \(k\).

18.5 Epilogue

When our generating function comes apart nicely into partial fractions, we can use the identity \(\frac{1}{1 - ax} = \sum a^n x^n\) to extract the coefficient of \(a^n\). More generally, we can handle generating functions like \(1 / (1 - ax)^k\) using the formulas of Section 13.4.

For something like \(x / (1 - x - x^2)\), partial fractions can be used to obtain \[ \frac{x}{1 - x - x^2} = \frac1{\sqrt5} \left( \frac{1}{1 - \phi x} - \frac{1}{1 - \psi x} \right); \text{ where } \phi, \psi = \frac{1 \pm \sqrt 5}{2}. \]

With the resulting formula \[ f_n = \frac{1}{\sqrt 5}(\phi^n - \psi^n). \] Known as Binet’s formula which we saw a version of in Section 11.3.1. This formula is super cool but computationally leaves a lot to be desired as multiplying large decimal numbers together can be quite expensive.

The fastest way to compute the Fibonacci sequence comes right from the recurrence definition. With a little bit of linear algebra, we can turn that linear recurrence into \[ \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} f_n \\ f_{n + 1} \end{pmatrix} = \begin{pmatrix} 0 f_n + f_{n + 1} \\ f_n + f_{n + 1} \end{pmatrix} = \begin{pmatrix} f_{n + 1} \\ f_{n + 2} \end{pmatrix}. \]

So the Fibonacci numbers and in fact, all of these linear recurrence relations, can be computed via matrix multiplication. This has the immediate advantage that we can use the identity \(A^{2n} = (A^n)^2\) to cut down our number of steps quite significantly. I.e. we have an algorithm where if \(n\) has \(k\) bits in binary, then the algorithm takes \(\mathcal O(k) = \mathcal O(\log_2 n)\) matrix multiplications.

Tip

The Sage commands for this look like

C = CFiniteSequences(ZZ)
Fib = C.from_recurrence([1, 1], [0, 1])
Fib.closed_form()
\(\displaystyle \sqrt{\frac{1}{5}} {\left(\frac{1}{2} \, \sqrt{5} + \frac{1}{2}\right)}^{n} - \sqrt{\frac{1}{5}} {\left(-\frac{1}{2} \, \sqrt{5} + \frac{1}{2}\right)}^{n}\)