# Formula for some average

I am finding a formula for the average $$A_n$$ of the numbers $$(a_1-a_2)^2 + \cdots + (a_{n-1} - a_n )^2$$ over all cases that $$\{a_1, \cdots, a_n \} = \{ 1,2, \cdots, n\}$$.

For example, $$A_2=1, A_3=4, A_4=10, A_5=20, A_6=35, \cdots$$. From this, I guess: $$A_n = \frac{1}{6} (n-1) n (n+1).$$

Can anyone prove it or give correct formula?

• are you sure the terms are $(1,3,10,20,35,.....)$ , cuz there not any OEIS for this Nov 26, 2021 at 10:39
• 3 should be 4. It's corrected now. Nov 26, 2021 at 10:55

From your results, one can coclude that you calculate average of all permutation of set. Then due to symmetry $$A_n=(n-1) B_n$$ , where $$B_n$$ is average of $$(a_1-a_2)^2$$ for all possible pairs $$(a_1,a_2)$$. $$B_n$$ could be found directly:
$$B_n=\frac{2}{n(n-1)}\sum_{a_1=1}^{n-1} \sum_{a_2=a_1+1}^{n} (a_1-a_2)^2=\frac{1}{6}n(n+1)$$
Then $$A_n=\frac{1}{6}n(n-1)(n+1)$$
• A bit more detailed: We want to compute $E[(a_1 - a_2)^2 + (a_2 - a_3)^2 + \dots + (a_{n-1} - a_n)^2]$. By linearity of expectation, this becomes $E[(a_1 - a_2)^2] + E[(a_2 - a_3)^2] + \dots + E[(a_{n-1} - a_n)^2]$. By symmetry, the $n-1$ terms are equal, so we simply need to find $(n-1)E[(a_1 - a_2)^2]$. Nov 26, 2021 at 11:48