Reading through "sorting and searching"in Donald Knuth The Art of Computer Programming. There's this property I don't get, thought it's said is easy to prove. If
$$ G_n(z) = I_n(0) + I_n(1) z + \ldots = \sum_{k\geq 0} I_n(k)z^k $$
then we have
$$ G_n(z) = \left(1+ z + \ldots + z^{n-1} \right) G_{n-1}(z), $$
I don't have a clue why that is true. Can you tell me why? If not can you just give me an hint?
By $I_n(k)$ we mean the number of permutation that have $k$ inversion, on a set of size $n$.
If $G_n(z) = \left(1+ z + \ldots + z^{n-1} \right) G_{n-1}(z) = \sum_{k=0}^{n-1} z^k G_{n-1}(z) $, I'll derive a recurrence for the $I_n(k)$.
$G_n(z) = G_{n-1}(z)\dfrac{1-z^n}{1-z} $ so $(1-z)G_n(z) = (1-z^n) G_{n-1}(z) $.
$\begin{array}\\ (1-z^m)G_n(z) &=(1-z^m)\sum_{k\geq 0} I_n(k)z^k\\ &=\sum_{k\geq 0} I_n(k)z^k-\sum_{k\geq 0} I_n(k)z^{k+m}\\ &=\sum_{k\geq 0} I_n(k)z^k-\sum_{k\geq m} I_n(k-m)z^{k}\\ &=\sum_{m-1 \ge k\geq 0} I_n(k)z^k+\sum_{k\geq m} (I_n(k)-I_n(k-m))z^{k}\\ \end{array} $
Therefore, using this with $m=1$ and $m=n$,
$\sum_{0 \ge k\geq 0} I_n(k)z^k+\sum_{k\geq 1} (I_n(k)-I_n(k-1))z^{k} =\sum_{n-1 \ge k\geq 0} I_{n-1}(k)z^k+\sum_{k\geq n} (I_{n-1}(k)-I_{n-1}(k-n))z^{k} $ or $I_n(0)+\sum_{k\geq 1} (I_n(k)-I_n(k-1))z^{k} =\sum_{n-1 \ge k\geq 0} I_{n-1}(k)z^k+\sum_{k\geq n} (I_{n-1}(k)-I_{n-1}(k-n))z^{k} $.
Therefore $I_n(0) = I_{n-1}(0)$, $I_n(k)-I_n(k-1) =I_{n-1}(k)$ for $1 \le k \le n-1$, and $I_n(k)-I_n(k-1) =I_{n-1}(k)-I_{n-1}(k-n)$ for $n \le k$.
Now see if you can derive these recurrences from the properties of permutations.
You can also derive a recurrence from $G_n(z) = G_{n-1}(z)\dfrac{1-z^n}{1-z} $.