I'm having some trouble understanding the solution that R. Stanley gives to the following:
Let $n\geq k \geq 0$ and let $E_{n,k}$ be the number of alternating permutations of $[n+1]$ that starts with $k+1$. Show that: $$ E_{n+1,k+1} = E_{n+1,k} + E_{n,n-k}. $$
Stanley gives the following hint: Show that $E_{n+1,k}$ is the number of alternating permutations of $[n+2]$ with first term $k+1$ and second term unequal to $k$, and that $E_{n,n-k}$ is the number of alternating permutations of $[n+2]$ with first term $k+1$ and second term $k$.
Can someone help me understand it?