Toward Explicit Formula from Recursion : Is Generating function "the only" answer?

Question

I am trying to draw the explicit formula of $S_n$ that is defined as below:

$S_n$ is the number of words of length n using 0,1 and 2 such that no two consecutive 0's occur.

---

Myself, as I had learned from the basic skills in combinatorics, just easily get to the point constructing recursive relation such that:

$$S_n = 2S_{n-1} + 2S_{n-2}$$

since $S_n$ splits up to disjoint two cases: one with no 0 at the last posit, and always 0 at the last locus, then there exist bijection between the former one and 1 or 2 at the n-th posit multiplied with $S_{n-1} $ cases, and also another bijection between the latter one and 1 or 2 at the n-1-th posit multiplied with $S_{n-2}$.

So If my given recursion is correct, next step is how could I go further into the formulating with what.

I superficially knows the concept of $OGF$, and $EGF$, and their formal definition. Generating function contains its sequential information in a form of coefficients with a corresponding polynomial degrees as an index (as far as I understand).

Now if I define $S_n$ a functional form, $s(n)$, generating function would be :

$$g(x) = \sum_{n=0}^{\infty}s(n)x^n$$

Then let's little bit refer to a few terms of $S_n$:

$$1, 3, 8, 22, ...$$

And revise the $g(x)$:

$$g(x) = \sum_{n=0}^{\infty}s(n)x^n =\sum_{n=2}^{\infty}s(n)x^n+3x+1=2\sum_{n=2}^{\infty}s(n-1)x^n+2\sum_{n=2}^{\infty}s(n-2)x^n+3x+1 $$

Now, it looks like the problem has been changed into solve the functional equation(I am not sure this is right term)

1) What should be the next step?

2) Is the generating function the only approach toward the explicit formula?

Answer 1

Let's assume, for the sake of argument, that your recurrence relation is correct. Notice it is of a very specific form: linear, homogeneous, constant-coefficient. So we can treat it in a manner analogous to the methods for linear constant-coefficient homogeneous ODE's.

Starting with $S_0 = a$, $S_1 = b$, $S_n = 2S_{n-1}+2S_{n-2}$, we assume our solution is of the form $r^n$, and we have: $$r^n = 2r^{n-1} + 2r^{n-2}$$ or $$r^2-2r-2 = (r-1)^2-3 = 0$$ This indicates that we have the following roots of the characteristic equation: $r = 1+\sqrt{3}$, $r = 1-\sqrt{3}$, and our solution is hence of the form:

$$S_n = c_1(1+\sqrt{3})^n + c_2(1-\sqrt{3})^n$$ Setting $n=0$, $S_0 = a$, and $n=1$, $S_1 = b$, we have: $$S_0 = c_1 + c_2 = a$$ $$S_1 = c_1(1+\sqrt{3}) + c_2(1-\sqrt{3}) = (c_1+c_2) + (c_1-c_2)\sqrt{3} = a+(c_1-c_2)\sqrt{3} = b$$ (Notice we use the first relation to simplify the second slightly)

We immediately conclude that: $$c_1+c_2 = a$$ $$c_1-c_2 = \frac{b-a}{\sqrt{3}}$$ And our coefficients are hence: $$c_1 = \frac{1}{2}\left(a+\frac{b-a}{\sqrt{3}}\right),\quad\quad c_2 = \frac{1}{2}\left(a-\frac{b-a}{\sqrt{3}}\right)$$ and our solution is then: $$S_n = \frac{1}{2}\left(a+\frac{b-a}{\sqrt{3}}\right)(1+\sqrt{3})^n + \frac{1}{2}\left(a-\frac{b-a}{\sqrt{3}}\right)(1-\sqrt{3})^n$$

As in your above example, assume $S_0 = 1 = a$, $S_1 = 3 = b$. The sequence we generate is then: $$\{1,3,8,22,60,164,448,1224,3344,9136,...\}$$ (This also allows you to do things like compute the 197th term, which is 104868469426569085732577150729898576235889082115592545033891653100711477046912718209024)

Unfortunately, if the recurrence is not of this special form, things become more complicated, but there are a number of good references on discrete mathematics which can build on these methods. (For instance, Concrete Mathematics by Knuth, Discrete Mathematics And Its Applications by Rosen, Discrete Mathematics by Gallier, Discrete Mathematics for Computer Scientists by Stein et al, ...)

(Your recurrence relation does appear to be correct, but I didn't check this since it didn't seem the main focus. Rather, I am only showing an alternative to generating functions in solving recurrence relations of this form, as well as giving some references in case you run across more general/complicated recurrences.)

Answer 2

\begin{align} g(x) &=2\sum_{n=2}^{\infty}s(n-1)x^n+2\sum_{n=2}^{\infty}s(n-2)x^n+3x+1 \\ &=2\sum_{n=1}^{\infty}s(n)x^{n+1}+2\sum_{n=0}^{\infty}s(n)x^{n+2}+3x+1 \\ &=2x(g(x) - 1)+2x^2g(x)+3x+1 \\ \end{align}

The next step, after what you have, is to shift the indices over by 1 and 2. For instance, in the first sum you have $$ \sum_{n = 2}^\infty s(n-1)x^{n} = s(1)x^2 + s(2)x^3 + \dots = \sum_{n = 1}^\infty s(n)x^{n + 1}. $$

The second step is to now factor out an $x$ and $x^2$ respectively and write the sums in terms of $g(x)$.

You can now solve this equation for $g(x)$:

$$ g(x) = \frac{1 + x}{1 - 2x - 2x^2}. $$

We then want to factor the denominator as $(1 - \alpha x)(1 - \beta x)$. As you can see, $\alpha$ and $\beta$ are the reciprocals to the roots of $1 - 2x - 2x^2$. So $\alpha$ and $\beta$ are the roots of $-2 -2x + x^2$, reversing the coefficients (show this!). These are $\alpha = 1 - \sqrt 3$ and $\beta = 1 + \sqrt 3$.

Now take the partial fraction decomposition:

$$ g(x) = \frac{1 + x}{1 - 2x - 2x^2} = \frac{A}{1 - \alpha x} + \frac{B}{1 - \beta x} $$

You can solve for $A$ and $B$ using this equation or by noting that

$$ \frac{A}{1 - \alpha x} + \frac{B}{1 - \beta x} = \sum_{n = 0}^\infty (A\alpha^n + B\beta^n)x^n $$

and comparing with $g(x) = s(0) + s(1)x + \cdots$ to get a system of equations which you can solve.

---

An alternative to the recurrence relation is to use a regular expression. The set of strings from the alphabet $\{0,1,2\}$ not containing $00$ is given by the regular expression

$$ \{1,2\}^*(0\{1,2\}^+)^*\{\varepsilon,0\} $$

which has the generating function

$$ \frac{1}{1 - 2x} \frac{1}{1 - x\frac{2x}{1 - 2x}} (1 + x) = \frac{1 + x}{1 - 2x - 2x^2}. $$

Answer 3

As an appendix to the other solutions, one eventually obtains

$$ S_n = \left(\frac{1}{2} + \frac{1}{\sqrt{3}}\right) \left(1 + \sqrt{3}\right)^n +\left(\frac{1}{2} - \frac{1}{\sqrt{3}}\right) \left(1 - \sqrt{3}\right)^n \enspace. $$ With a little patience, this can be turned into

$$ S_n = \sum_{0 \leq k \leq n/2} \frac{2n-2k+1}{2k+1} \, \binom{n}{2k} \; 3^k \enspace.$$

Answer 4

This is where signals & systems knowledge comes in handy. :-)

Eigenvectors are your friend.

\begin{align*} S_n &= 2 S_{n-1} + 2 S_{n-2} \\ \\ \begin{bmatrix} S_n \\ S_{n - 1} \end{bmatrix} &= \begin{bmatrix} 2 & 2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} S_{n - 1} \\ s_{n - 2} \end{bmatrix} \end{align*}

Let $\vec{S}_{n+1} = \begin{bmatrix} S_n \\ S_{n-1} \end{bmatrix}$. We now have:

\begin{align*} \vec{S}_{n+1} &= \begin{bmatrix} 2 & 2 \\ 1 & 0 \end{bmatrix} \vec{S}_{n} \\ \\ \implies\ \ \ \vec{S}_{n+1} &= \begin{bmatrix} 2 & 2 \\ 1 & 0 \end{bmatrix}^n \vec{S}_1 \end{align*}

We're basically done at this point, but you can compute the power explicitly by diagonalizing it:

\begin{align*} \begin{bmatrix} 2 & 2 \\ 1 & 0 \end{bmatrix} x &= \lambda x \implies \lambda = 1\pm\sqrt{3} \\ \begin{bmatrix} 2 & 2 \\ 1 & 0 \end{bmatrix} &= \begin{bmatrix} 1 + \sqrt{3} & 1 \\ 1 - \sqrt{3} & 1 \end{bmatrix} \begin{bmatrix} 1 + \sqrt{3} & 0 \\ 0 & 1 - \sqrt{3} \end{bmatrix} \begin{bmatrix} 1 + \sqrt{3} & 1 \\ 1 - \sqrt{3} & 1 \end{bmatrix}^{-1} \\ \end{align*}

So this means we have our answer $S_n$ in the first row of $\vec{S}_{n+1}$:

\begin{align*} \vec{S}_{n+1} &= \begin{bmatrix} 1 + \sqrt{3} & 1 \\ 1 - \sqrt{3} & 1 \end{bmatrix} \begin{bmatrix} (1 + \sqrt{3})^n & 0 \\ 0 & (1 - \sqrt{3})^n \end{bmatrix} \begin{bmatrix} 1 + \sqrt{3} & 1 \\ 1 - \sqrt{3} & 1 \end{bmatrix}^{-1} \vec{S}_1 \end{align*}