I am working through Ryan O' Donnell's book on the analysis of Boolean functions. One of the exercises (1.1) is to compute the Fourier series of the `complete quadratic function' on $\mathbf{F}_2^n$
$$ CQ(x) = (-1)^{\sum_{i < j} x_i x_j} $$
Without any fancy harmonic analysis terminology, the problem asks us to calculate the expectations
$$\widehat{f}(S) = \mathbf{E}[CQ(X)(-1)^{\sum_{i \in S} x_i}]$$
for any subset $S \subset \{ 1, \dots, n \}$, where $X$ is uniformly distributed on $\mathbf{F}_2^n$, in which case we can write
$$ CQ(x) = \sum_{S \subset [n]} \widehat{f}(S) (-1)^{\sum_{i \in S} x_i}$$
An important first step to solving the problem is noticing that $CQ(x)$ depends only on the number of indices $i$ such that $x_i = 1$. That is, $CQ(x) = 1$ if and only if $n(n-1)$ is divisible by 4. However, I can't seem to get anywhere from this. This makes it easy to compute the expectation of $CQ(x)$ (though I can't seem to see a nice `general' formula, I've just broken down the analysis depending on $n$'s congruence class modulo 4). In order to calculate $\widehat{f}(S)$ in general, I've tried calculating the expectation by condition on both $(-1)^{\sum_{i \in S} x_i} = \pm 1$, and conditioning on the latter gives (assuming $S$ has $m$ elements)
$$ \mathbf{E}(CQ(X) (-1)^{\sum_{i \in S} x_i} = (1/2^n) \sum_{k = 0}^m \sum_{l = 0}^{n-m} (-1)^k {m \choose k} {n - m \choose l} r_{k+l} $$
where $r_x = 1$ if $x$ is congruent to 0 or 1 (mod 4), and $r_x = -1$ if $x$ is congruent to 2 or 3 (mod 4). But my knowledge of binomial identities is really rusty and I don't know how to reduce the sum any further. Any guidance?