Number of walks How many walks (asymptotically) of length $2n$ with up or right steps from $(0,0)$ to $(n,n)$ are there such that the walk is always between the lines $y=x+k$ and $y=x-k$?
 A: The number is very small. Here is a possible approach.     Here we assume $n\gg k$ and we denote a walk with the constraints you mention as admissible.    Given any walk  of length $L$  and $j\in \{1,\dotsc, L\}$  we denote by  $(H_j, V_j)$ the location at time $j$. Thus $H_j$ is the number of horizontal steps taken up to the moment $j$ and similarly, and $V_j$ is the number  of vertical steps taken up to the time $j$. A path is admissible if $-k\leq V_j-H_j\leq k$, $\forall j$. $V_{2n}=H_{2n}=n$.
To a walk $W$  in the lattice $\newcommand{\bZ}{\mathbb{Z}}$ $\bZ^2$ we  associate a walk $W'$  in the lattice $\bZ$  starting at $0$ as $0$. If at time  $j$ in $W$  we take a vertical steps, then in $W'$ we move one unit to the right. If at time $j$ in $W$ we take a horizontal step, then in  $W'$ we take a step to the left.   
Now think of the walks in $\mathbb{Z}^2$  as random walks where the  horizontal/vertical steps  have the same probability.    We have thus associated to a random walk $W$ in $\bZ^2$ a standard one-dimensional  walk $W'$ on $\bZ$. The walk $W$ is admissible if and only if the corresponding walk $W'$ starts and ends  at $0$ and never leaves the   interval $[-k,k]$.   Denote by $T(W')$ the first moment steps outside the interval $[-k,k]$.  The probability that $T(W')> 2n$ is known.     Walks in the interval $[-k-1,k+1]$ with absorbing boundary seem relevant. (I have to leave.)
Edit. Had a busy weekend. I have two comments.
1. Ira Gessels's   comment answers the original question more precisely than my speculations above.
2. My above speculations can still be used to  provide an asymptotic  estimate  for $n$ large.  More precisely if $W_k(n)$ is the number of walks from $(0,0)$ to $(n,n)$ that do not cross the lines $y=x\pm k$, then
$$ W_k(n)\sim \left(\;  2\cos\frac{\pi}{2k+2}\;\right)^{2n}\;\;\mbox{as}\;\;n\to \infty. $$
This approach  also yields an explicit expression in terms of Chebyshev polynomials for the generating function of the number of walks from $(0,0)$ to $(n,n)$ that do cross the lines $y=x\pm k$; see (3).  Here are the details. 
Denote by $p_k(n)$ the probability that  a random walk on $\bZ$ starts and ends  at $0$ after $2n$ steps  and never  reaches the locations $\pm(k+1)$. Form the generating series
$$ P_k(x)=:\sum_{n\geq 0} p_k(n)x^{2n}. $$
Using the  idea  of the random walk on $[-(k+1),(k+1)]$ with absorbing boundary one can give an explicit description of $P_k(x)$ as a  rational function.
For any natural number $m$ denote by $Q_m$ the $m\times m$  symmetric matrix with entries
$$q_{ij}=\begin{cases}\frac{1}{2}, &|i-j|=1\\
0, & |i-j|\neq 1.
\end{cases}. $$
Then $p_k(n)$ is equal to the $(k+1,k+)$-entry of the matrix $Q_{2k+1}^{2n}$, i.e., the   entry of this odd-sized matrix located dead in the center. (This is not hard to see. Alternatively, check any book on Markov chains. $Q$ corresponds to the transient part of this Markov chain.)
This shows that  $P_k(x)$ is the $(k+1,k+1)$ entry of the matrix $(1-xQ)^{-1}$  and from the expression of a the entries of the inverse of a matrix in terms of the minors of the matrix we deduce
$$P_k(x)=\frac{\det(1-xQ_k)^2}{\det(1-xQ_{2k+1})}. $$
The special shape of the matrices  $Q_m$  leads to a recursive computations of the determinants of $1-xQ_m$. Hint: the matrix $1-xQ_m$ is a Jacobi matrix and,  if $D_m(x):=\det(1-xQ_m)$, then
$$D_m(x)=D_{m-1}(x)-\frac{x^2}{4} D_{m-2}(x). $$
This leads to an explicit, albeit  complicated  expression of $P_k(x)$ in terms of Chebyshev polynomials; see (2).
In any case the above  expression shows that  the asymptotic behavior of $p_{k}(n)$ is determined by  the eigenvalues of $Q_{2k+1}$. It is not hard to see that the spectrum of this symmetric matrix is contained   in $(-1,1)$.  $\DeclareMathOperator{\spec}{spec}$  If
$$\Lambda_k=\max\bigl\{\; |\lambda|;\;\;\lambda\in\spec(Q_{2k+1})\;\bigr\}<1,  $$
then we deduce that 
$$ p_k(n)=O(\Lambda_k^{2n}), \;\;n\to\infty. $$
I believe that  
$$p_k(n) \sim C_k\Lambda_k^{2n}, $$
so the asymptotics of the number of walks you asked about would be
$$\sim C (2\Lambda_k)^{2n}. $$
The spectrum of $Q_m$  is known. More precisely
$$\spec Q_m =\Bigl\{ \cos \frac{k\pi}{m+1};\;\;k=1,\dotsc, m\;\Bigr\}. $$
For details see  these beautiful answers to a MO question.  Thus
$$ p_k(n) \sim C_k\Bigl(\cos\frac{\pi}{2k+2}\Bigr)^{2n}, \tag{1} $$
for some constant $C_k$   described explicitly in (4) below.
Remark.  Let us denote by $W_k(n)$ the number of East-North   walks in the lattice $\bZ^2$ which start at $(0,0)$, end at $(n,n)$ and do not cross the lines $y=x\pm k$. We form the generating series
$$W_k(x)=\sum_{n\geq 0} W_k(n)x^{2n}. $$
Then
$$W_k(x) =P_k(2x). $$
Let us express $P_k(x)$ in terms of the characteristic polynomials $\Delta_m(x)$ of the matrices $Q_m$. We have
$$D_m(x)=\det(1-xQ_m)= x^m \det(x^{-1}-Q_m) =x^m \Delta_m(x^{-1}). $$
We have
$$\Delta_m(x)= x\Delta_{m-1}(x)-\frac{1}{4}\Delta_{m-2}(x). $$
In particular, if $S_m(x)=2^{m} \Delta_m(x)$,  then we deduce that
$$S_m(x)= 2xS_{m-1}(x) -S_{m-2}(x). $$
This is precisely the recurrence relation satisfied by the Chebyshev polynomials $T_m(x)$, $U_m(x)$ defined by
$$ T_m(\cos \theta)=\cos(m\theta),\;\;U_m(\cos\theta)=\frac{\sin(m+1)\theta}{\sin\theta}. $$
Note that
$$ S_1(x) =2x=U_1(x), \;\; S_2(x)=4x^2-1=U_2(x). $$
Hence $S_m(x)=U_m(x)$ so that
$$\Delta_m(x)=\frac{1}{2^m} U_m(x),\;\; D_m(x)=\left(\frac{x}{2}\right)^m U_m(1/x), $$
$$ D_m(2x)= x^m U_m\left(\frac{1}{2x}\right), $$
$$P_k(x)=\frac{4}{x^2}\frac{U_k(1/x)^2}{U_{2k+2}(1/x)},\;\;\tag{2} $$
$$  W_k(x)= \frac{U_{k}\bigl(\frac{1}{2x}\bigr)^2}{x^2 U_{2k+2}\bigl(\frac{1}{2x}\bigr)}. \tag{3} $$
We can say something about the constant $C_k$ in (1) by observing that
$$ D_m(x) =A_m\prod_{j=1}^m\left(1-x\cos\frac{j\pi}{m+1}\right), $$
for some constant $A_m$.  More precisely 
$$ A_m=2^{-m}\times \mbox{ the leading coefficient of $U_m$}=1.$$
Then
$$ P_k(x)= \frac{A_k^2}{A_{2k+2}}\frac{\prod_{j=1}^k (1-x\cos\frac{j\pi}{k+1})}{\prod_{\ell=1}^{k+1}(1-x\cos \frac{(2\ell-1)\pi}{2k+2})}. $$
This shows that 
$$ C_k=\frac{A_k^2}{A_{2k+2}}=1.\tag{4} $$
Update 2. As I suspected all along, this problem has been thoroughly investigated.  There is a comprehensive discussion of this and other problems in  Chapter XIV, Sect. 4,5  vol 1 of Feller's book. This problem  also makes its appearance in  the Kolmogorov-Smirnov statistics test; see  Chap I, Sec. 12, vol. 2 of Feller's book on probability., or Feller's article On the Kolmogorov-Smirnov limit theorems for empirical distributions, Ann. Math. Statistics, 19(1948), 177-189.
