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.
Best Answer
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.