Ordering elements from $\{0, 1, 2, 3, ..., k\}$ s.t. that the difference between $2$ consecutive elements is $0$ or $1$? 
In how many ways can you order (with repetition) elements from $\{0, 1, 2, 3, ...,
k\}$ in $s > k + 1$ spots such that the difference between $2$ consecutive elements is $0$
or $1$?

These are some of my ideas:

*

*Define $s-1$ new variables (call them $m_i$) that represent the differences between $2$ consecutive numbers. Now think of the number of ways of ordering $0$'s and $1$'s across these $m_i$'s and the number of ways to get $a_{i + 1} - a_i = m_i$ where $a_i \in \{0, 1, 2, 3, ..., k\}$. The problem with this is that I'm not being able to account for the fact that the $a_{i + 1}$ for $m_i$ is equal to the $a_{i}$ for $m_{i + 1}.$

*Stars and Bars: Sum over all possible summations of the $m_i$'s listed above where all possible bounds on the variables are considered. In the best case, this perhaps yields nested sums.

*Principle of inclusion-exclusion: There are $s^{k + 1}$ total permutations, representing the universal set. Of these, I need to find the union of all permutations s.t. the difference between $2$ elements is not $0$ nor $1$. The number of sets and intersections to consider is making this a big challenge.

*Recursion: This has the problem of not necessarily being a linear constant-coefficient homogeneous relation which can reduce the likelihood of forming a general formula. Moreover, I'm unable to construct one.

Fundamentally, I'm unable to break down this question into accessible cases to work with.  What I find especially frustrating is that choosing a $0$ or $k$ gives $2$ possible choices for the next number while all the numbers in between give $3$ choices. Accounting for every case while the pattern changes sporadically is something I'm not being able to control.
 A: Your problem can be stated in terms of graph theory. Consider the graph whose vertex set is $\{0,1,\dots,k\}$, where two vertices $x,y\in \{0,\dots,k\}$ are connected by an edge if and only if $|x-y|\le 1$ (meaning there is a loop joining every vertex to itself). Then your problem is equivalent to counting the number of walks of length $s-1$ in this graph (the length of a walk is the number of edges, which is one less than the number of vertices).
Let $A_k$ be the $(k+1)\times(k+1)$ matrix where $A_{ij}=1$ when $|i-j|\le 1$, and $A_{ij}=0$ otherwise. This is the adjacency matrix for this graph. It is well known that the number of walks of length $\ell$ from vertex number $i$ to vertex number $j$ in a graph with adjacency matrix $A$ is the $(i,j)$ entry of $A^\ell$. Therefore, the answer to your question is
$$
\sum_{i=0}^k\sum_{j=0}^k(A^{s-1})_{i,j}
$$
Equivalently, if we let ${\bf 1}=[1\;1\;\dots\;1]$ be the row vector with $k+1$ ones, then the number of sequences is
$$
{\bf 1}\cdot A^{s-1}\cdot {\bf 1}^\top
$$
