I want to check that whether my method of solving this problem is right. Here is my solution:
I want to use inclusion-exclusion to solve this. Suppose
$P_1=$ the case that I put one of the elements from $\{0,1,2,3\}$ to the end of the string , resulting $12$ occurs
$P_2=$ the case that I put one of the elements from $\{0,1,2,3\}$ to the end of the string, resulting $20$ occurs
$P_1\cap P_2=$ the case that I put one of the elements from $\{0,1,2,3\}$ to the end of the string, resulting $12$ and $20$ occur
I use $h_n$ to denote the number of strings that follows the requirement.
First, I suppose the first $n-1$ string is okay, and I just add one of $\{0,1,2,3\}$ to the end. Thus I have $$\begin{align*} 4h_{n-1} \end{align*}$$ as the number of strings.
Then I consider case $P_1$. It can happen iff the string looks like $$\begin{align*} \cdots |1,() \end{align*}$$ $\cdots$ denote the frist $n-2$ string and the second-to-last position is $1$ , so when adding $2$ to the last, $12$ occurs. On the other hand, first $n-2$ string is okay; similarly, this also explains the case of $P_2$ so we have $$\begin{align*} 2h_{n-2} \end{align*}$$ cases.
Finally, consider $P_1 \cap P_2$. That is, I add one of $\{0,1,2,3\}$ to the end, and I get both $12$ and $20$. This can only happen if I have the string looks like $$\begin{align*} \cdots |1,2,() \end{align*}$$ and I add $0$ to the end. This time, the first $n-3$ string is okay. Thus such case is $$\begin{align*} h_{n-3} \end{align*}$$ By inclusion-exclusion, the result is $$\begin{align*} h_{n}=4h_{n-1}-2h_{n-2}+h_{n-3} \end{align*}$$ I believe the answer is right, but I doubt my method. Any help on this? Thanks.
You got the correct answer, but your explanation does not make sense to me. The universe for your application of PIE is the set of strings counted by $4h_{n-1}$, which is the set of strings of the form $$ s_{n-1}\mid x, $$ where $s$ is a string of length $n-1$ with no instances of $12$ or $20$, and $x\in \{0,1,2,3\}$. You then seem to be saying that $P_1$ is the set of strings in the above form which contain $12$, and $P_2$ is the set of strings in the above form which contain $20$. You are correct when you say that $|P_1|=h_{n-2}$. However, it is not correct to say that $|P_1\cap P_2|=h_{n-3}$. Instead, $|P_1\cap P_2|$ is empty. Indeed, the case $s_{n-3}\mid 1,2,\,\_\_$ you mentioned cannot occur in $P_1\cap P_2$, because that would mean that $s_{n-1}$ ended with $1,2$, which violates our definition of $s_{n-1}$.
Instead, what is happening here is that $$ |P_2|=h_{n-2}-h_{n-3},\qquad |P_1\cap P_2|=0 $$ To count $|P_2|$, note that in order for $20$ to appear in $s_{n-1}\mid x$, it must appear at the very end, meaning that $x=0$ and $s_{n-1}=w_{n-2}\mid 2$. However, we cannot let $w_{n-2}$ be an arbitrary string of length $n-2$ which avoids $12$ and $20$. We need to insist that $w_{n-2}$ does not end with $1$, else it would form $12$ with the following $2$. Therefore, using the word "valid" to mean "not containing $12$ or $20$", $$ \begin{align} |P_2| &=\text{# valid strings of length $n-2$ not ending in $1$} \\&=(\text{# valid strings of length $n-2$})-(\text{# valid strings of length $n-2$ ending in 1}) \\&=h_{n-2}-h_{n-3}\end{align} $$ The reason that the number of valid strings of length $(n-2)$ ending with $1$ is $h_{n-3}$ is that deleting the $1$ at the end is a bijection with valid strings of length $(n-3)$.