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?$ 



A follow up question to: Number of walks on integer lattice with self-edge at zero
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.$$


