1
$\begingroup$

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?

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

1 Answer 1

4
$\begingroup$

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)$$

$\endgroup$
1
  • 3
    $\begingroup$ 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]$. $\endgroup$
    – VTand
    Nov 26, 2021 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.