Recurrence Relation for the number of lattice paths with an even number of N moves

Question

The Full Question

Find a recurrence for the number of lattice paths beginning at $(0,0)$ with steps N and W, and which contain an even number of N steps.

My Work

A string of length $n$ can end in W or N. If it ends in W, all we are doing is adding W to the end of a string of length $n-1$. If it ends in N, then the $n-1$ sting before it must have an odd number of N moves. All strings of length n-1 with an odd number of steps is just all the possible strings minus all the strings with even N, mathematically put: $2^{n-1}-a_{n-1}$.

$a_n = 2^{n-1}$ By rule of sum

But this is not correct because we know $a_3 = 2 \neq 2^2$

Where did I go wrong in my reasoning, and can anyone suggest a better approach?

Answer 1

Your argument is correct; you simply miscounted the valid paths of length $3$. As noted in the comments, there are four of them: WWW, WNN, NWN, and NNW.

Note that you don’t actually need a recurrence here. Suppose that $n>0$, and $s_1s_2\ldots s_n$ is a path, not necessarily valid, of length $n$. The N steps can occupy any subset of the $n$ positions in the path. There are $2^n$ such subsets, and half of them have even cardinality, so $a_n=2^{n-1}$. (Of course, you can view your argument as another proof of the fact that half of the subsets of a non-empty finite set have even cardinality.)