For any $n ≥ 1$ and $1 ≤ k ≤ n$, define the “Eulerian number” $e(n, k)$ to be the number of permutations of $\{1, 2, . . . , n\}$ with exactly $k −1$ descents. So $e(n, 1) = e(n, n) = 1$, and $e(n, k) = 0$ if $k < 1$ or $k > n$. Prove that $e(n, k) = k · e(n − 1, k) + (n − k + 1)e(n − 1, k − 1)$, for all $n ≥ 1$ and $1 ≤ k ≤ n$. Use the recurrence to find $e(n, k)$ for all $k$, with $n ≤ 5$.
I am thinking of breaking it down into a permutation of $[n − 1]$ with either $k − 1$ or $k − 2$ descents, but I'm not sure how to prove the number of ways to insert $n$.