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?