Number of Motzkin paths with no horizontal steps at positive heights Let $a(n,k)$ be the number of all Motzkin paths of length $n$ with $k$ down-steps and no horizontal steps at positive heights.   OEIS A008315 states that $a(n,k)=\binom{n}{k}-\binom{n}{k-1}.$
Where can I find a simple proof of this fact?
 A: Let $A(n,k)$ be the set of Motzkin paths you describe.
Let $B(n,k)$ be the set of walks from $(0,0)$ to $(n,n-2k)$ whose steps are all $(1,1)$ or $(1,-1)$, and which never go below the $x$ axis.
Define $f:A(n,k)\to B(n,k)$ as follows. Given a Motzkin path, replace all of the horizontal steps on the ground with $(1,1)$ steps. For example,
                              /\/
 /\               ==>    /\  /
/  \ _ _ /\ _           /  \/
   
    A(9, 3)              B(9, 3)

I claim that $f$ is a bijection. The inverse map is this: given a path $P$ in $B(n,k)$, call an up step from $(x,y)$ to $(x+1,y+1)$ "critical" if $P$ never returns to a height of $y$ after that step. Replacing all critical up steps in $P$ with horizontal steps gives a path $Q$ in $A(n,k)$ for which $f(Q)=P$.
Finally, the reflection principle allows you to enumerate paths in $B(n,k)$ to be exactly $\binom nk-\binom n{k-1}$. That is, take the set of all $\binom{n}k$ paths from $(0,0)$ to $(n,n-2k)$, and subtract out the bad paths which at some point go below the $x$ axis. If you reflect that bad paths at the first time they dip below, you get a bijective correspondence to all paths from $(0,0)$ to $(n,2k-n-2)$, counted by $\binom{n}{k-1}$.
