I want to find the number of paths of length $2n$ that start and end at $(0,0)$ in the diagram below (Just to be clear, each step is between connected nodes, so for example $(0,0)$ to $(0,2)$ is not allowed):
Clearly, any such path would have an even number of steps. Having counted paths of length $2$, $4$, and $6$, it appears that for length $2n$, there are $2^{2n-1}$ paths.
I thought of it this way: A step in which the $y$ coordinate increases, I call "North" or just "$N$". The opposite is "South" or "$S$".
Then we need to count the number of sequences of length $2n$ that satisfy the following:
- An equal number of $N$s and $S$s ($n$ of each).
- The sequence starts with $N$.
- At no point in the sequence can the number of $N$s exceed the number of $S$s by $3$ or more.
- At no point in the sequence can the number of $S$s exceed the number of $N$s.
Counting the sequences of length $2$ is easy: The sequence looks like $\{N,S\}$, and since there are $2$ choices for the first $N$, there are $2$ sequences.
Notice now that in general, every odd-numbered step in any sequence will have $2$ options.
The length $4$ sequences are $\{N,S,N,S\}$ which represents $4$ different paths, and $\{N,N,S,S\}$ which represents another $4$, for a total of $8$.
For length $6$, each of the below sequences represents $8$ different paths, for a total of $32$:
$\{N,S,N,S,N,S\}, \{N,S,N,N,S,S\}, \{N,N,S,S,N,S\}, \{N,N,S,N,S,S\}$
At this point, it becomes tedious to list all the possible sequences. For length $8$, I would predict $2^{8-1}=128$ different paths, and so on.
I'm sure I am overlooking some kind of insight that makes the counting easier and/or explains why I am correct. I appreciate any input!
This is equivalent to counting the lattice paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$ that consist of steps from $\langle x,y\rangle$ to $\langle x+1,y\pm 1\rangle$, never drop below the $x$-axis, and never rise above the line $y=2$. Let $a_n$ be the number of such paths.
Suppose that $p$ is such a path. There is a largest $k<n$ such that $\langle 2k,0\rangle$ is on $p$. There are $a_k$ ‘legal’ paths from $\langle 0,0\rangle$ to $\langle 2k,0\rangle$, and there is only one ‘legal’ path from $\langle 2k,0\rangle$ to $\langle 2n,0\rangle$ that hits the $x$-axis only at those two points. Thus,
$$a_n=\sum_{k=0}^{n-1}a_k\;.\tag{1}$$
Clearly $a_0=1$, and we immediately calculate that $a_1=1$, $a_2=2$, $a_3=4$, and $a_4=8$, leading to your conjecture that $a_n=2^{n-1}$ for $n\ge 1$. This is easily verifed from $(1)$ by induction: if $a_0=1$ and $a_k=2^{k-1}$ for $1\le k<n$, then
$$a_n=\sum_{k=0}^{n-1}a_k=1+\sum_{k=1}^{n-1}2^{k-1}=1+\sum_{k=0}^{n-2}2^k=1+(2^{n-1}-1)=2^{n-1}\;.$$