An verification about the solution of problem relating recursive relations 
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.
 A: 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)$.
