Closed form of this nested sum with variable lower bound

Question

I would like to know why the closed form expression of

$$\sum_{i=1}^{n}\sum_{j=i+1}^{n} (a_i + a_j)^2 + (b_i + b_j)^2$$

evalutes to

$$ (n-2) \cdot \sum_{i=1}^{n} (a_i^2 + b_i^2) + (\sum_{i=1}^{n} a_i)^2 + (\sum_{i=1}^{n} b_i)^2$$.

The problem poster offered us to use the substitution $s = \sum_{i=1}^{n} a_i$.

I am assuming that when $i=n$, the lower bound is larger than the higher bound, and the sum has a value $0$ so can be neglected (thus upper bound of the outer sum is actually up to $i = n-1$, but I left it in original form in case I am wrong).

I tried to expand the inner sum over $j$ into $\sum_{j=1}^{n}(\cdot) - \sum_{j=1}^{i}(\cdot)$ but it did not seem to help simplify terms.

Source: Codeforces global round 19 problem D. You can see his explanation under question 1637D https://codeforces.com/blog/entry/99883

Answer 1

It suffices to show that $$\sum_{i=1}^n \sum_{j=i+1}^n (a_i + a_j)^2 = (n-2)\sum_{i=1}^n a_i^2 + \left(\sum_{i=1}^n a_i \right)^2$$ Observe that \begin{align} \sum_{i=1}^n \sum_{j=i+1}^n (a_i + a_j)^2 &= \sum_{i=1}^n a_i^2(n-i) + \sum_{i=1}^n\sum_{j=i+1}^n a_j^2 + \sum_{i=1}^n 2a_i \sum_{j=i+1}^n a_j\\ &= \sum_{i=1}^n a_i^2(n-i) + \sum_{i=2}^n (i-1)a_i^2 + \sum_{i=1}^n 2a_i \sum_{j=i+1}^n a_j\\ &= (n-2)\sum_{i=1}^n a_i^2 + \sum_{i=1}^n a_i^2 + \sum_{i=1}^n 2a_i \sum_{j=i+1}^n a_j\\ &= (n-2)\sum_{i=1}^n a_i^2 + \sum_{i=1}^n a_i^2 + 2 \sum_{i=1}^n \sum_{j=i+1}^n a_ia_j\\&= (n-2)\sum_{i=1}^n a_i^2 + \left(\sum_{i=1}^n a_i \right)^2 \end{align} as $$ \sum_{i=1}^n \sum_{j=i+1}^n a_j^2 = \sum_{i=2}^n (i-1)a_i^2 $$ and $$\left(\sum_{i=1}^n a_i \right)^2 = \sum_{i=1}^n a_i^2 + 2 \sum_{i=1}^n \sum_{j=i+1}^n a_ia_j$$ where the latter equality follows from the multinomial theorem. Similarly, you can show that $$\sum_{i=1}^n \sum_{j=i+1}^n (b_i + b_j)^2 = (n-2)\sum_{i=1}^n b_i^2 + \left(\sum_{i=1}^n b_i \right)^2$$ which implies the desired result.

---

Remark. To better understand $$ S: =\sum_{i=1}^n \sum_{j=i+1}^n a_j^2 = \sum_{i=2}^n (i-1)a_i^2 $$ observe that $S$ is just the sum of all entries of the following matrix: $$A = \left[\begin{matrix}0 & a_2^2 & a_3^2 & a_4^2 & \ldots & a_n^2\\ 0 & 0 & a_3^2 & a_4^2 &\ldots & a_n^2\\ 0 & 0 & 0 & a_4^2 &\ldots & a_n^2 \\ \vdots & \vdots & \vdots & \ddots & a_{n-1}^2 & a_n^2\\ 0 & 0 & 0 & 0 & 0 & a_n^2\end{matrix}\right]_{n-1\times n}$$

Answer 2

First, notice that : $$\begin{array}{lcl} \displaystyle \left(\sum_{i = 1}^n a_i\right)^2 & = & \displaystyle \sum_{i = 1}^n a_i \sum_{i = 1}^n a_i \\[3mm] & = & \displaystyle \sum_{i = 1}^n \sum_{j = 1}^n a_i a_j \\[3mm] & = & \displaystyle \sum_{i = 1}^n a_i^2 + \sum_{i = 1}^n \sum_{j = 1}^{i - 1} a_i a_j + \sum_{i = 1}^n \sum_{j = i + 1}^n a_i a_j \\[3mm] & = & \displaystyle \sum_{i = 1}^n a_i^2 + \sum_{j = 1}^n \sum_{i = 1}^{j + 1} a_i a_j + \sum_{i = 1}^n \sum_{j = i + 1}^n a_i a_j \\[3mm] & = & \displaystyle \sum_{i = 1}^n a_i^2 + \sum_{i = 1}^n \sum_{j = 1}^{i + 1} a_i a_j + \sum_{i = 1}^n \sum_{j = i + 1}^n a_i a_j \\[3mm] & = & \displaystyle \sum_{i = 1}^n a_i^2 + 2 \sum_{i = 1}^n \sum_{j = i + 1}^n a_i a_j \\[3mm] \end{array}$$ We deduce that : $$\begin{array}{lcl} \displaystyle \sum_{i = 1}^n \sum_{j = i + 1}^n (a_i + a_j)^2 & = & \displaystyle \sum_{i = 1}^n \sum_{j = i + 1}^n (a_i^2 + a_j^2 + 2 a_i a_j) \\[3mm] & = & \displaystyle \sum_{i = 1}^n (n - i) a_i^2 + \sum_{i = 1}^n \sum_{j = i + 1}^n a_j^2 + 2 \sum_{i = 1}^n \sum_{j = i + 1}^n a_i a_j \\[3mm] & = & \displaystyle \sum_{i = 1}^n (n - i) a_i^2 + \sum_{j = 1}^n \sum_{i = 1}^{j - 1} a_j^2 + 2 \sum_{i = 1}^n \sum_{j = i + 1}^n a_i a_j \\[3mm] & = & \displaystyle \sum_{i = 1}^n (n - i) a_i^2 + \sum_{j = 1}^n (j - 1) a_j^2 + 2 \sum_{i = 1}^n \sum_{j = i + 1}^n a_i a_j \\[3mm] & = & \displaystyle \sum_{i = 1}^n (n - i) a_i^2 + \sum_{i = 1}^n (i - 1) a_i^2 + 2 \sum_{i = 1}^n \sum_{j = i + 1}^n a_i a_j \\[3mm] & = & \displaystyle \sum_{i = 1}^n (n - 1) a_i^2 + 2 \sum_{i = 1}^n \sum_{j = i + 1}^n a_i a_j \\[3mm] & = & \displaystyle \sum_{i = 1}^n (n - 2) a_i^2 + \sum_{i = 1}^n a_i^2 + 2 \sum_{i = 1}^n \sum_{j = i + 1}^n a_i a_j \\[3mm] & = & \displaystyle \sum_{i = 1}^n (n - 2) a_i^2 + \left(\sum_{i = 1}^n a_i^2\right)^2 \\[3mm] \end{array}$$