I was trying to solve this problem:
bob wants to write the numbers $1, 2, \dots, 9, 10$ on a paper. first he writes $1$. then in order from $i = 2$ to $i = 10$, he writes $i$ like this: there is a $\frac{1}{2}$ chance that he will write it before the first number, a $\frac{1}{2^j}$ chance that he will write it between the $j-1$th and $j$th number that he has already written (for any $j\in \{2, 3, \dots, i - 1, i\}$) and a $\frac{1}{2^{i-1}}$ chance that he will write it after the last number. an inversion is a pair of distinct numbers from $\{1,2,\dots,9,10\}$ such that the bigger one is written before the other one in the written permutation. what is the expected value of the number of inversions in the written permutation?
sorry if the problem statement is unclear. I needed to translate it from another language.
my approach: Let $e_{n}$ be the expected number of inversions in the written permutation if bob wrote the numbers $1,2,\dots ,n-1,n$. we proof that $e_{n + 1} = {n \choose 2} - \frac{1}{2^{n}} + 1$. if $n = 1$ then the given formula gives $\frac{1}{2}$ which is correct. assume that for $n$ the given formula is correct. using this we prove that it is also correct for $n + 1$ (mathematical induction). if we don't consider $n + 1$ in the written permutation then the expected value of the number of inversions is just $e_n$. now let's focus on $n + 1$. if there are $k$ numbers in front of it, then it will be in exactly $k$ inversions. because $n + 1$ is the last number that bob writes there is a $\frac{1}{2^{n + 1-k}}$ chance that there will be $k$ numbers in front of it (we don't consider the special case where $k = 0 $ because then $n + 1$ wouldn't make an inversion with any other number). using this and the properties of expected values we get the recursive formula $$e_{n+1} = e_{n} + \sum_{k = 1}^{n}k\frac{1}{2^{n + 1-k}} = {n-1 \choose 2} - \frac{1}{2^{n-1}} + 1 + \sum_{k = 1}^{n}k\frac{1}{2^{n + 1-k}}$$ with the base $e_2 = \frac{1}{2}$. if we prove that $\sum_{k=1}^{n}\frac{k}{2^{n + 1 - k}} = n + \frac{1}{2^n} - 1$ then the problem is solved because ${n \choose 2} = {n-1 \choose 2} + n - 1$ and $-\frac{1}{2^{n}} = -\frac{1}{2^{n - 1}} + \frac{1}{2^n}$ . but i cant find a way to prove it. you can also see that this is true because of this.
Maybe I'm making it hard for no reason, so if you have any other method to solve the problem please post it.
Hint: There is a very easy way to prove such identities. Let $$ f(x)=\sum_{k=0}^n x^k=\frac{1-x^{n+1}}{1-x}. $$ Then $$ f'(x)=\sum_{k=0}^n k x^{k-1}=\sum_{k=1}^n k x^{k-1}=\frac{1-(n+1)x^n+nx^{n+1}}{(1-x)^2}. $$ Can you take it from here?