IMC 2008 · Day 1 · P6

Consider the $n \times n$ determinant $$\Delta(x) = \begin{vmatrix} 1 & x & \dots & x^{n-1} \\ x & 1 & \dots & x^{n-2} \\ \vdots & \vdots & \ddots & \vdots \\ x^{n-1} & x^{n-2} & \dots & 1 \end{vmatrix}$$ where the $ij$-th entry is $x^{|i-j|}$. From the definition of the determinant we get $$\Delta(x) = \sum_{(i_1, \dots, i_n) \in S_n} (-1)^{\operatorname{inv}(i_1, \dots, i_n)} x^{D(i_1, \dots, i_n)}$$ where $S_n$ is the set of all permutations of $(1, 2, \dots, n)$ and $\operatorname{inv}(i_1, \dots, i_n)$ denotes the number of inversions in the sequence $(i_1, \dots, i_n)$. So $Q(n, d)$ has the same parity as the coefficient of $x^d$ in $\Delta(x)$.

It remains to evaluate $\Delta(x)$. In order to eliminate the entries below the diagonal, subtract the $(n-1)$-th row, multiplied by $x$, from the $n$-th row. Then subtract the $(n-2)$-th row, multiplied by $x$, from the $(n-1)$-th and so on. Finally, subtract the first row, multiplied by $x$, from the second row. $$\Delta(x) = \begin{vmatrix} 1 & x & \dots & x^{n-2} & x^{n-1} \\ x & 1 & \dots & x^{n-3} & x^{n-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ x^{n-2} & x^{n-3} & \dots & 1 & x \\ x^{n-1} & x^{n-2} & \dots & x & 1 \end{vmatrix} = \dots = \begin{vmatrix} 1 & x & \dots & x^{n-2} & x^{n-1} \\ 0 & 1 - x^2 & \dots & x^{n-3} - x^{n-1} & x^{n-2} - x^n \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 - x^2 & x - x^3 \\ 0 & 0 & \dots & 0 & 1 - x^2 \end{vmatrix} = (1 - x^2)^{n-1}.$$ For $d \ge 2n$, the coefficient of $x^d$ is 0 so $Q(n, d)$ is even.