I have not heard of this identity before I am trying to increase my math abilities by working through the solutions of past Putnam exam problems. I am currently working on Putnam 1985-2a. I have been able to work through to the last part of this problem where I currently have:
1 - $\sum_{i=1}^n(a^2_i)$
and all that's left to find is the minimal value of this expression. (EDIT: Minimum value for $\sum_{i=1}^n(a^2_i)$ so that I can obtain the maximum value of the term possible given that $a_i>0$ and $a_{1} + \dots + a_{n} =1$).
I am currently working on using the C-S inequality to do this. In the answer to the problem they give a lot of examples of how to find this, but I am curious about the following identity that they don't name. This is the identity:
$n(a_{1}^2 + \dots + a_{n}^2) = (a_{1}+\dots+a_{n})^2 +\sum_{i<j}(a_{i}-a_{j})^2$
The summation looks a little like how we calculate variance, but I don't know where this identity comes from, or if it has a name. Can anyone help?
Thanks.
 A: This is a special case of Lagrange's identity:
$$ \Big(\sum_{k=1}^n a_k^2\Big)\Big(\sum_{k=1}^n b_k^2\Big) -
   \Big(\sum_{k=1}^n a_k b_k\Big)^2 = \sum_{k=1}^{n-1}\sum_{j=i+1}^n
  (a_ib_j-a_jb_i)^2 \tag{1} $$
where all of the $\,b_k=1\,$ which results in
$$ n \Big(\sum_{k=1}^n a_k^2\Big) -
   \Big(\sum_{k=1}^n a_k\Big)^2 = \sum_{1\le i<j\le n}  (a_i-a_j)^2. \tag{2} $$
Divide both sides of this equation by $\,n^2\,$ and change $\,a_k\,$
into $\,x_i\,$ to get
$$ \text{Var}(X) = \frac1n \Big(\sum_{i=1}^n x_i^2\Big) -
   \Big(\frac1n \sum_{i=1}^n x_i\Big)^2 = \frac1{n^2}\sum_{1\le i<j\le n}  (x_i-x_j)^2 \tag{3} $$
an equation which is almost exactly what appears in the Wikipedia
Variance article.
A: So first, let me say that it is quite easy to see geometrically/show using Lagrange multipliers, that the maximum of $\sum a_i^2$ on the simplex $\{\sum a_i = 1 : a_i \ge 0\}$ occurs when all but one of the variables are $0$. The Lagrange condition $\lambda \nabla f = \nabla g$ is $2\lambda a_i = 1$ so either $a_i = 0$ or $a_i = \frac{1}{2\lambda}$ (all the non-zero $a_i$'s are equal) now you can just check if there are $k$ variables which are non-zero then the value is
$$ k \left( \frac{1}{k} \right)^{2} = \frac{1}{k}.$$
Therefore the maximum occurs when $k = 1$. This avoids having to guess at some symmetric function identity that does exactly what you want.
Then for the symmetric function identity, it just boils down to expanding the right hand side.
$$ \left( \sum a_i \right)^2 = \sum a_i^2 + 2 \sum_{i < j} a_i a_j$$
and
$$
\sum_{i < j} (a_i - a_j)^2 = \sum_{i < j} a_i^2 - 2 \sum_{i < j} a_i a_j + \sum_{i < j} a_j^2 = (n - 1) \sum a_i^2
$$
since $a_k^2$ appears once for each $j > k$ and once for each $i < k$ (so for every index except $k$).
