A follow up question to: Number of walks on integer lattice with self-edge at zero

Question

Let $a(n)$ be the number of lattice paths in ${\mathbb{Z}^2}$ of length $n$ which start at the origin $(0,0)$ and end up at $(n,0)$ and have only up-steps $U:(i,j) \to (i + 1,j + 1)$, down-steps $D:(i,j) \to (i + 1,j - 1)$ and horizontal steps $H:(i,0) \to (i + 1,0)$ on the $x-$axis. Is there a direct combinatorial way (i.e. without use of generating functions) to show that $a(n) = \sum\limits_{k = 0}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {\frac{{{2^k}(n - 1)!!}}{{k!(n - 1 - 2k)!!}}} $ or of the special case $a(2n+1)=5^n?$

Answer 1

Let me explain why $a(2n+1)=5^n$. I need a well-known identity $\sum_{a+b=n}\binom{2a}{a}\binom{2b}{b}=4^n$, which has nice combinatorial proofs. Now we prove that the number of walks of length $2n+1$ from 0 to 0, in which every step is $+1$, $-1$ or staying at 0 (call this a loop) equals $5^n$. Induction in $n$, base $n=0$ is clear. There are exactly $4^n$ such paths with exactly 1 loop, it follows from the above identity. For other paths, there are at least 2 loops (at least 3 actually). Let us count paths with $2k$ steps before the first loop and $2m$ steps after the last loop. The number of such paths equals $\binom{2k}k\binom{2m}m5^{n-k-m-1}$ (by induction). Fix $k+m=s$ and sum up by pairs $(k,m)$ with given sum, we get $4^s 5^{n-1-s}$ again by the identity. It remains to note that $$\sum_{s=0}^{n-1}4^s5^{n-1-s}=\frac{5^n-4^n}{5-4}=5^n-4^n.$$

Answer 2

The idea of Fedor Petrov led me to the following proof of the above formula.

In arXiv:1203.5424 R. Duarte and A. G. de Oliveira gave a combinatorial proof of the identity $$S_m(k)=\sum_{i_1+\dots+i_m=k}\binom{2i_1}{i_1}\dots\binom{2i_m}{i_m}=4^k\binom{k+m/2-1}{k}.$$ If we attach a horizontal step $H$ at the beginning then each such path has a uniquely determined decomposition in the form ${L_{{a_1}}}{L_{{a_2}}} \cdots {L_{{a_m}}}$ where ${L_a} = H{M_a}$ and ${M_a}$ is a path of length $2a$ starting and ending on height $0$ with $a$ up-steps and $a$ down-steps. Therefore $\sum\limits_{i = 1}^m {\left( {1 + 2{a_i}} \right) = n + 1} $ or if we set $\sum\limits_{i = 1}^m {{a_i} = k} $ then $m = n + 1 - 2k.$ The number of such paths is ${S_{n + 1 - 2k}}(k) = {4^k}\binom{\frac{{n - 1}}{2}}{k}.$ Summing over all $k$ gives the above result.