On: A strange determinant – Timothy Gowers solves a pr...

[sverona]

You got the right idea. The sum vanishes once $k > \min{i, j}$, so WLOG if $i \geq j$ you've got $\sum_{k=0}^j \binom{i}{k}\binom{j}{j - k}$, which is equal to $\binom{i + j}{j}$ by Vandermonde's identity [0], which is well-known enough that you can reliably expect people working in combinatorics to recognize it on sight. This goes through for every entry of the product, actually, so there's your proof.

[0] https://en.wikipedia.org/wiki/Vandermonde%27s_identity

[delhanty → sverona]

Essentially then, the LU decomposition of P is just the matrix form of Vandermonde’s - which I recall now.

So I’m surprised that Timothy Gowers didn’t just write that down.