Simplify Permutation Inversion Count Recurrence Let $I_{n, k}$ denote the number of permutations $\pi \in S_n$ with exactly $k$ inversions. Using the convention $I_{n, k} = 0$ for $k < 0$ and $\displaystyle k > \frac{n(n - 1)}{2}$, we first have the well-known sum
$\displaystyle I_{n, k} = \sum_{j = 0}^{n - 1} I_{n - 1, k - j}$
which can be derived by considering the position of element $1$. But there is a second recurrence:
$\displaystyle I_{n, k} = I_{n, k - 1} + I_{n - 1, k} - I_{n - 1, k - n}$
How to derive this formula? Is there a way to obtain it from the above sum using algebraic reasoning?
 A: Here is an algebraic proof using
$$I_{n,k} = [x^k] \prod_{p=0}^{n-1} \sum_{q=0}^p x^q.$$
We show that
$$I_{n,k} - I_{n,k-1} = I_{n-1,k} - I_{n-1, k-n}.$$
We get for the LHS
$$[x^k] \prod_{p=0}^{n-1} \sum_{q=0}^p x^q
- [x^{k-1}] \prod_{p=0}^{n-1} \sum_{q=0}^p x^q
= [x^k] \prod_{p=0}^{n-1} \sum_{q=0}^p x^q
- [x^k] x \prod_{p=0}^{n-1} \sum_{q=0}^p x^q
\\ = [x^k] (1-x) \prod_{p=0}^{n-1} \sum_{q=0}^p x^q.$$
For the RHS we find
$$[x^k] \prod_{p=0}^{n-2} \sum_{q=0}^p x^q
- [x^{k-n}] \prod_{p=0}^{n-2} \sum_{q=0}^p x^q
= [x^k] \prod_{p=0}^{n-2} \sum_{q=0}^p x^q
- [x^k] x^n \prod_{p=0}^{n-2} \sum_{q=0}^p x^q
\\ = [x^k] (1-x^n) \prod_{p=0}^{n-2} \sum_{q=0}^p x^q
= [x^k] (1-x) \sum_{q=0}^{n-1} x^q \prod_{p=0}^{n-2} \sum_{q=0}^p x^q
\\ = [x^k] (1-x) \prod_{p=0}^{n-1} \sum_{q=0}^p x^q.$$
This is the same as the LHS as claimed.
A: This is sort of an extended hint. Given a combinatorial interpretation of the summands in
$$
I_{n, k} = \sum_{j = 0}^{n - 1} I_{n - 1, k - j},
$$ 
try to use that to interpret combinatorially the following:
$$
\begin{split}
I_{n, k} 
&= I_{n-1,k} + \sum_{j=1}^{n-1}{I_{n-1,k-j}}\\
&= I_{n-1,k} + \sum_{j=0}^{n-2}{I_{n-1,k-j-1}}\\
&= I_{n-1,k} + \sum_{j=0}^{n-1}{I_{n-1,k-1-j}}-I_{n-1,k-n}\\
&=I_{n-1,k}+I_{n,k-1}-I_{n-1,k-n}.
\end{split}
$$
