Counting The Number Of K-Bounded Good Lists Of Length N Problem Statement: 
A k-bounded list of length n is a sequence [x1, x2, . . . , xn] where each xj
is an
integer between 0 and k, inclusive. A good list is one that does not contain three
consecutive values 0, 1, 0. For example, for n = 4 and k = 2, [2, 0, 0, 1] and [1, 0, 0, 1]
are good lists while [0, 1, 0, 2] and [0, 0, 1, 0] are not.
Let good(n, k) be the number of good k-bounded lists of length n. For instance,
the good 1-bounded lists of length 2 are {[0, 0], [0, 1], [1, 0], [1, 1]}, so good(2, 1) = 4.
Similarly, you can check that good(4, 1) = 12 and good(3, 2) = 26.
Your task is to compute good(n, k) for the following values of n and k.
(a) good(7, 1) 
(b) good(7, 3) 
(c) good(20, 1) 
Note: This is a question from a past contest and the official answers for the parts a, b and c are as follows:
(a) good(7, 1) = 65 
(b) good(7, 3) = 15163 
(c) good(20, 1) = 97229 
My Approach: I came up with the following recurrence relations, 
$$p(i,0) = p(i-1,0) + p(i-1,1) - p(i-2,0)$$ $$p(i,1) = [p(i-1,0) + p(i-1,1)]\times k$$
where $p(i,0)$ is the number of good lists of length $i$ ending with 0 and $p(i,1)$ is the number of good lists of length i not ending with 0. The idea behind this is that every good list of length $i$ is an extension of a good list of length $i-1$ but there can also be some bad extensions in the process, hence it is better to handle them separately. Therefore, in case a good list ends with 0,1 then we need to take care of the fact that while extending this list we don't count the lists where we place a 0 at the end, otherwise we will have 0,1,0 in the list. So what we do is that we just count all the lists of length $i$ ending with 0 and then subtract the lists of length $i-2$ that end with a 0. Whereas the case where we do not use a 0 at the end is a bit simpler.
I just filled the table for the above recurrence manually with the initial values as $p(0,0) = 0$, $p(0,1) = 0$, and $p(1,0) = 1$,  $p(1,1) = k$ (since it was a pen and paper exam) and could arrive at the answers which is the sum of $p(n,0)$ and $p(n,1)$ [C++ code for reference: https://ideone.com/wSVhVL]. But then I have been thinking whether this problem has a closed form solution, some function in n and k. I couldn't arrive at one until now. Can anyone provide some combinatorial insight? Is a closed form solution possible?
 A: I am going to use Chomsky-Schutzemberger method to find the generating function of this (you put DP as tag, so I guess you are interested in computational stuff). Consider the following automaton that accepts the good lists.


If you label $A,B,C,D$ the nodes of the automaton, then the following system of equations gives you the generating function of the number of strings of size $n$ that the automaton accepts.
$$A=1+kxA+xB, \, B=xB+xC+(k-1)xA+1,C=\, kxA+1.$$
We omit $D$ because is a state that dies. Doing the substitution, you get
$$(1-kx)A=1+xB=1+x\frac{x+kx^2A+(k-1)xA+1}{1-x},$$
So $$A=\frac{1+\frac{x^2+x}{1-x}}{1-kx-\frac{kx^3+(k-1)x^2}{1-x}},$$
hence $$A=\frac{1+x^2}{(1-x)(1-kx)-(kx^3+(k-1)x^2)}=\frac{1+x^2}{1-(k+1)x+x^2-kx^3}=\frac{1}{1-\left ( kx+\frac{x}{1+x^2}\right ) }.$$
This agrees with your findings. One can try to factor the denominator to try to use partial fractions and get a formula. The problem is that this polynomial does not seem to have a nice factorization (for low $k'$s) that would be enough evidence to me that a "nice close formula" is not possible. OEIS just seems to have $k=1$.
Case k=1:
The OEIS gives that
$$a_n = \sum_{k=0}^{n+2} \binom{n+2-k}{2k}.$$
which says that somehow a tiling problem can be attach to this(reminds me of Fibonacci).

General case:
A very ugly but closed formula can be seen to be
$$a_n=\sum _{i=0}^n\sum _{\substack{a_0+2a_1+4a_2+\cdots +2\ell \cdot a_{\ell}+\cdots =n-i\\ a_0+a_1+\cdots =i}}\frac{i!}{\prod _{j=0}^{\infty} a_j!}(k+1)^{a_0}(-1)^{a_1+a_3+\cdots +a_{2\ell 
 +1}+\cdots }$$
A: I believe that this is from a hand-written Computing contest, where you're expected to use algorithms to evaluate these finite cases. If so, the goal is to come up with a simple equation to describe the scenario, and then iterate to the corresponding $n,k$ values.
Fill in the gaps as needed, especially when it says "Show that". If you're stuck, explain what you've tried and why it doesn't seem to work.

Let

*

*$A_k (n)$ be the number of $k-$bounded lists of length $n$ that end with $0$.

*$B_k (n)$ be the number of $k-$bounded lists of length $n$ that end with $0, 1$.

*$C_k (n)$ be the number of $k-$bounded lists of length $n$ that end with "not $0$, and not $0,1$".

We are after $A_k (n) + B_k(n) + C_k(n)$.
Show that we have the recurrence relations

*

*$A_k(n+1) = A_k(n) + C_k(n)$.

*$B_k(n+1) = A_k(n)$

*$C_k (n+1) = (k-1) A_k (n)  +  (k) B_k (n) + (k) C_k(n)  $
Show also that we have the initial values

*

*$A_k(2) = k+1 $

*$B_k(2) = 1 $

*$C_k(2) = (k+1)^2 - (k+1) - 1 = k^2 + k -1$.


For example, here is good$(7,3)$.

A: The following answer is based upon the Goulden-Jackson Cluster Method which provides a convenient technique to solve problems of this kind. We consider the set of words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{A_0,A_1,\ldots, A_{k}\}$$ of size $k+1$ and the set $B=\{A_0A_1A_0\}$ containing a bad word of length $3$, which is not allowed to be part of the words we are looking for.

Generating function $f_k(t)$: We derive a generating function $f_k(t)$ with the coefficient of $t^n$ being  the number of wanted words of length $n$.
According to the paper (p.7) the generating function $f_k(t)$  is
\begin{align*}
f_k(t)=\frac{1}{1-(k+1)t-\text{w}(\mathcal{C})}\tag{1}
\end{align*}
with $k+1=|\mathcal{V}|$ the size of the alphabet and $\text{w}(\mathcal{C})$ the weight-numerator of bad words with
\begin{align*}
\text{w}(\mathcal{C})=\text{w}(\mathcal{C}[A_0A_1A_0])\tag{2}
\end{align*}

We calculate according to the paper:
\begin{align*}
\text{w}(\mathcal{C}[A_0A_1A_0])&=-t^{3}-t^2\text{w}(\mathcal{C}[A_0A_1A_0])\tag{3}\\
\end{align*}
where the expression $t^2\text{w}(\mathcal{C}[A_0A_1A_0])$ accounts for overlappings of $A_{0}A_1A_0$ with itself. We obtain from (3):
\begin{align*}
\text{w}(\mathcal{C}[A_0A_1A_0])&=-\frac{t^3}{1+t^2}
\end{align*}
It    follows from (1) - (3):
\begin{align*}
\color{blue}{f_k(t)}&=\frac{1}{1-(k+1)t-\text{weight}(\mathcal{C})}\\
&=\frac{1}{1-(k+1)t+\frac{t^3}{1+t^2}}\\
&\,\,\color{blue}{=\frac{1+t^2}{1-(k+1)t-t^2-kt^3}}\tag{4}
\end{align*}
and conclude the number of valid words of length $n\geq 0$ is the coefficient of $t^n$ in (4).

Coefficient extraction: We use the coefficient of operator $[t^n]$ to denote the coefficient of $t^n$ of a series. Applying standard techniques to extract the coefficient $[t^n]$ from $f_k(t)$ we obtain for $n\geq 2$:
\begin{align*}
\color{blue}{[t^n]f_k(t)}&\color{blue}{=\sum_{j=0}^{n}(-1)^j\sum_{l=0}^j\binom{n-j}{l}\binom{l}{j-l}k^{j-l}(k+1)^{n-j-l}}\\
&\qquad\color{blue}{+\sum_{j=0}^{n-2}(-1)^j\sum_{l=0}^j\binom{n-2-j}{l}\binom{l}{j-l}k^{j-l}(k+1)^{n-2-j-l}}\tag{5}
\end{align*}
Calculation: We derive from (5)
\begin{align*}
\color{blue}{[t^7]f_1(t)}&=\sum_{j=0}^{7}(-1)^j\sum_{l=0}^j\binom{7-j}{l}\binom{l}{j-l}2^{7-j-l}\\
&\qquad+\sum_{j=0}^{5}(-1)^j\sum_{l=0}^j\binom{5-j}{l}\binom{l}{j-l}2^{5-j-l}
\color{blue}{=65}\\
\color{blue}{[t^7]f_3(t)}&=\sum_{j=0}^{7}(-1)^j\sum_{l=0}^j\binom{7-j}{l}\binom{l}{j-l}3^{j-l}4^{7-j-l}\\
&\qquad+\sum_{j=0}^{5}(-1)^j\sum_{l=0}^j\binom{5-j}{l}\binom{l}{j-l}3^{j-l}4^{5-j-l}
\color{blue}{=15\,163}\\
\color{blue}{[t^{20}]f_1(t)}&=\sum_{j=0}^{20}(-1)^j\sum_{l=0}^j\binom{20-j}{l}\binom{l}{j-l}2^{20-j-l}\\
&\qquad+\sum_{j=0}^{18}(-1)^j\sum_{l=0}^j\binom{18-j}{l}\binom{l}{j-l}2^{18-j-l}\color{blue}{=97\,229}\\
\end{align*}
which has been programmatically verified.
