How many sequences of $L$s and $R$s of length $n$ have no consecutive subsequences where $|\#L -\#R| > k$? This question popped up in discussion with a colleague, and I'm anxious to take a crack at it.
Given some sequence of $L$s and $R$s, how many such sequences of length $n$ have no consecutive subsequences such that difference between the amount of $L$s and $R$s is more than a given integer $k$? A consecutive subsequence of some sequence $a_{n}$ is a subsequence $a_{n_{k}}$ such that $\forall k, n_{k+1}-n_{k} =1$.
Example:
$n = 10,k = 2$.
$RRLRRLLRLR$.
This sequence does not satisfy the condition, because the consecutive subsequence $RRLRR$ has $4$ $R$s and $1$ $L$, resulting in a difference of $3$.
Considering the sequence $RLRRLLRLR$, however, when $n = 9$ and $k=2$, one sees that the sequence satisfies the condition as no consecutive subsequence has a difference of more than $2$.
My question is to solve this for general $n,k$. I've tried some work with recursive relations, but I keep running into roadblocks. I don't know of any other simpler methods to solve this, but that's why I'm asking here! 
 A: You could begin by counting left-right paths of length $n$ that start at $(x_0,0)$ for some $0 \le x_0 \le k$, end at $(x_n,n)$ for some $0 \le x_n \le k$, get from one to the other by steps of $(+1,+1)$ and $(-1,+1)$, and never cross the lines $x=0$ and $x=k$. 
This is not the problem you want to solve, but it is related. All sequences with no subsequence on which $|\#L - \#R| > k$ can be expressed in this way by starting at some point $(x_0,0)$, interpreting $L$ as $(-1,+1)$ and $R$ as $(+1,+1)$. Moreover, if a sequence has $\max |\#L - \#R| = j$, where the max is taken over all subsequences, then there are $k-j+1$ starting points we can choose.
So if we have a formula for the number of these paths, we get the formula you want just by some inclusion-exclusion. Moreover, you're not going to be missing out on a nicer formula, this way, because for very large $n$ and fixed $k$, asymptotically almost all sequences with no subsequence on which $|\#L - \#R| > k$ do have a subsequence on which $|\#L - \#R| = k$, and can be expressed in only one way by these left-right paths.
Left-right paths starting at $(i,0)$ and ending at $(j,n)$ are given by the corresponding entry of $$\begin{bmatrix}0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0  & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0\end{bmatrix}^n$$ except more generally with $k+1$ rows instead of $5$. This matrix has eigenvalues $2\cos \frac{\pi j}{k+2}$ for $1 \le j \le k+1$ and correspondingly nice eigenvectors, so you'll be able to get a formula in terms of powers of these eigenvalues for any fixed $k$; I'm not sure if there's a nice expression for general $k$.
