Number of walks of given length issued from one point in a (N,E,W) grid system I understand how this idea works. Use the Binomial theorem and plug in the two numbers on the point for North and East into the binomial equation, but my specific problem deals with the possibility of going west too. Here's the specific problem he gave us
 
 A: Enumerating the results for small $n$ :

$n=1$
$E,N,W$
Total $3$

$n=2$
$EE,EN,NE,NN,NW,WN,WW$
Total $7$

$n=3$
$EEE,EEN,ENE,ENN,ENW,NEE,NEN,NEW,NNE,NNN,NNW,NWN,NWW,WNE,WNN,WNW,WWN,WWW$
Total $17$

$n=4$
$EEEE,EEEN,EENE,EENN,EENW,ENEE,ENEN,ENNE,ENNN,ENNW,ENWN,ENWW,NEEE,NEEN,NENE,NENN,NENW,NNEE,NNEN,NNNE,NNNN,NNNW,NNWN,NNWW,NWNE,NWNN,NWNW,NWWN,NWWW,WNEE,WNEN,WNNE,WNNN,WNNW,WNWN,WNWW,WWNE,WWNN,WWNW,WWWN,WWWW$
Total $41$

We can see that the number of length-$n$ walks starting with $N$ equals the total number of length-$(n-1)$ walks... And the number of length-$n$ walks starting with $E$ equals the number of length-$(n-1)$ walks starting with $N$ or $E$... And the total number of length-$n$ walks is the sum of those starting with $N$ and $E$ and $W$.
Define the number of walks starting with $N$ as $a_n$, and with $E$ (or $W$) as $b_n$. Then the total is $a_n+2b_n$, and
$$a_n = a_{n-1}+2b_{n-1}$$
$$b_n = a_{n-1}+b_{n-1}$$
and of course $a_1=b_1=1$. This completely determines the sequences $a_n$ and $b_n$.
This is a first-order linear system, which can be written with matrices as
$$\begin{bmatrix} a_n\\b_n \end{bmatrix} = \begin{bmatrix}1&2\\1&1 \end{bmatrix}\begin{bmatrix}a_{n-1}\\b_{n-1}\end{bmatrix}$$
and has the solution
$$=\begin{bmatrix}1&2\\1&1 \end{bmatrix}^n\begin{bmatrix}a_0\\b_0\end{bmatrix}$$
where $a_0=1,b_0=0$.

Sequence of powers of the matrix:
$$\begin{bmatrix}1&0\\0&1\end{bmatrix},\begin{bmatrix}1&2\\1&1\end{bmatrix},\begin{bmatrix}3&4\\2&3\end{bmatrix},\begin{bmatrix}7&10\\5&7\end{bmatrix},\begin{bmatrix}17&24\\12&17\end{bmatrix},\begin{bmatrix}41&58\\29&41\end{bmatrix},\begin{bmatrix}99&140\\70&99\end{bmatrix},\begin{bmatrix}239&338\\169&239\end{bmatrix},\begin{bmatrix}577&816\\408&577\end{bmatrix},\begin{bmatrix}1393&1970\\985&1393\end{bmatrix},\begin{bmatrix}3363&4756\\2378&3363\end{bmatrix},\cdots$$
It can be diagonalized for a more explicit formula (thanks @ploosu2) :
$$\begin{bmatrix}1&2\\1&1\end{bmatrix}^n = \frac14\begin{bmatrix}-\sqrt2&\sqrt2\\1&1\end{bmatrix}\begin{bmatrix}(1-\sqrt2)^n&0\\0&(1+\sqrt2)^n\end{bmatrix}\begin{bmatrix}-\sqrt2&2\\\sqrt2&2\end{bmatrix}$$
$$= \begin{bmatrix}\frac12\Big((1+\sqrt2)^n+(1-\sqrt2)^n\Big)& \frac{\sqrt2}2\Big((1+\sqrt2)^n-(1-\sqrt2)^n\Big)\\ \frac{\sqrt2}4\Big((1+\sqrt2)^n-(1-\sqrt2)^n\Big)&\frac12\Big((1+\sqrt2)^n+(1-\sqrt2)^n\Big)\end{bmatrix}$$
Now, the desired number is
$$a_{n+1} = \frac12\Big((1+\sqrt2)^{n+1}+(1-\sqrt2)^{n+1}\Big)$$
$$= \sum_k\binom{n+1}{2k}2^k$$
