The coin flipping pattern problem: We flip coins until a given pattern (e.g., $THTTH$) ($T$ for tail and $H$ for head) is first obtained. What is the expected number of flips?
The first solution uses the law of total expectation (wiki):
The automaton for the pattern $THTTH$ is shown below.
We define $S_i$ to be the expected number of flips to reach the state $s_i$. Then, we have
\begin{align*} S_0 &= \frac{1}{2}(1 + \pmb{S_0} + 1 + S_1) \\ S_1 &= \frac{1}{2}(1 + \pmb{S_1} + 1 + S_2) \\ S_2 &= \frac{1}{2}(1 + \pmb{S_0} + 1 + S_3) \\ S_3 &= \frac{1}{2}(1 + \pmb{S_2} + 1 + S_4) \\ S_4 &= \frac{1}{2}(1 + \pmb{S_1} + 1 + S_5) \\ S_5 &= 0 \end{align*}
Solving this set of linear equations, we get our desired result $S_0 = 36$.
The second solution uses the formula developed in the book "Concrete Mathematics", Section 8.4 based on probability generating function (wiki).
Given a pattern of length $n$, the expected number of flips to first obtain it is given by the formula: $$2(\sum_{k=1}^{n} 2^{k-1}[A^{(k)} = A_{(k)}]),$$ where $A^{(k)}$ and $A_{(k)}$ denote respectively the last $k$ characters and the first $k$ characters of $A$, and $[A^{(k)} = A_{(k)}] = 1$ if $A^{(k)}$ is the same with $A_{(k)}$, otherwise $[A^{(k)} = A_{(k)}] = 0$.
For example, for $A=THTTH$, the expected number of flips is: $$2(2^1 + 2^4) = 36,$$ since $A^{(2)} = TH = A_{(2)}$ and $A^{(5)} = THTTH = A_{(5)}.$
My Question: How to relate the set of linear equations in the first solution to the formula in the second solution?
Specifically, can you obtain the formula $2(\sum_{k=1}^{n} 2^{k-1}[A^{(k)} = A_{(k)}])$ used in the second solution by solving the set of linear equations (for any pattern) in the first solution?
Note that the set of linear equations to solve in the first solution is easy to list: Only the part in bold (the backward states) are different for different patterns.
This is not a complete answer to this question, but here's what I think: put on out Linear Algebra hat and try to find out something. I'll explain the idea in the example you gave but it follows easily to a general form of the problem. First, we substitute $S_5=0 $ in the previous equation and we write everything in matrix form, let $x=(S_0, S_1, S_2, S_3, S_4) $ we get :
$$x= \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}+\frac{1}{2}\begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \end{bmatrix}x $$ Now letting $A=\begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \end{bmatrix} $ we can write this equation as $$ (I-\frac{1}{2}A)x=\begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix} $$ Now, I won't really prove this fact, but you can show that $\frac{1}{2}A$ is definitely nilpotent, this means that every coefficient $(\frac{1}{2}A)^k$ goes arbitrary close to $0$ as $k$ grows, this is because the $1/2^k$ at the denominator is enough to carry every coefficient to $0$.
Now we use a lemma about nilpotent elements in (this works of every ring) the matrix ring: if $N$ is a nilpotent element of order $k$ then $(I-N)$ admit inverse and it's $ (I-N)^{-1}=I+N+N^2+N^3+ \dotsc + N^k $.
For us, $k$ will be $+\infty$ but it doesn't change the substance. We go straightforward and invert matrix $\frac{1}{2}A$ in our equation: $$ x=(I-\frac{1}{2}A)^{-1}\begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}=\left( \sum_{k=0}^{\infty} \frac{1}{2^k}A^k \right)\begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}$$ Now since we are searching $S_0$ we care about the first component of our equation, we let $M_{(1)} $ to be the first raw of matrix $M $. $$ S_0=x_{(1)}=\left( \sum_{k=0}^{\infty} \frac{1}{2^k}A^k_{(1)} \right)\begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}=\sum_{k=0}^{\infty} \frac{1}{2^k}\left( A^k_{(1)}\begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix} \right)=\sum_{k=0}^{\infty} \frac{1}{2^k}\left(\sum_{j=1}^5 a_{1j}^{(k)} \right) $$
Here's where i stop, because looking our last equation makes me suggest that we are deep inside using generating funcions, and if we move on with our reasosing and try to evaluate that sum finding a recursive relation between $a^{(k)}_{1j} $we would finish definitely using generating function.
PS: a step that maybe can go little further in the computation is this: you can note that $A=S_5+B$ where $S_5 $ is the shift matrix of order $5$ and it's trivial to show it's nilpotent of order $5$. Now it only remains $B$ that only depends on the given pattern we are using. In this particular case you can see that $B^2$ is something like a projection matrix (in particular $B$ seems to verify that $B^2=B^3=B^4 \dotsc$), i don't know if this is true in general. If it's true this would make the direct solution and computation really simple Without using generating functions. Maybe viewing $B$ as an incidence matrix of a directed graph leads to this conclusion.