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

Solution 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.)

Solution 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}. $$

Solution 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.$$

Solution 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*}