I'm stuck on this linearity of expectation problem. My final answer didn't make sense I checked through my calculations a few times. I think I am solving this wrong.
Suppose we have a permutation $m$ of numbers $1,2,...,n$. We then insert each number of $m$ one by one into a binary search tree (where all nodes on the left are smaller than the parent and larger numbers on the right of the parent) where the first element of the permutation is the root.
I would like to find the expected value for the size of the sub-tree rooted at number 1.
My observations lead to some facts that the 1 must always be on the left side of the tree (unless it is root). If 1 is on the $i$-$th$ position, the possible elements under 1 can in the positions $i+1,...,n$ where they must be smaller than positions $1,..,i-1$.
Let $X$ be a random variable representing the size of the tree at 1.
$$E(X) = \sum_{i=1}^n E(X_i)$$ Where $E(X_i) = \sum_{j=i}^n j\cdot P(X_i = j)$ is the expected value of tree size when 1 is at position $i$.
So I define some indicator variables; $$ j =\begin{cases}1 & \textit{less than elements from 0 to i - 1 (is a record)}\\0 & otherwise \end{cases} $$
and the probability of element $i$ being a record, smaller than all elements from $0,..,i-1$... (I think the probability may be wrong) I tried to express all possible ways to order elements past $i+1$ with $(n-i+1)!$ and the possible elements greater than $i$ with $\frac{1}{i}$. The expected number of records from $o,..,i=n$ of a random permutation is $H_n$. $$P(X_i=j) = \frac{\frac{1}{i}\cdot (n-i+1)!}{n!}$$ Then putting it together should be: $$E(X) = \sum_{i=1}^n \sum_{j=i}^n \frac{\frac{1}{i}\cdot (n-i+1)!}{n!}$$
I left out solving the summation.
I don't think you're working with expectations the right way. The most powerful idea behind expectations is the linearity of expectation: $\Bbb E[X_1+\cdots+X_n]=\Bbb E[X_1] + \cdots + \Bbb E[X_n]$. Separating cases based on the position of $i$ in the permutation does not take full advantage of this.
Suppose $X$ is the number of elements under $1$ in the tree. To take advantage of linearity of expectation, let's define $X_i$ to be $1$ if element $i$ is under $1$, and $0$ otherwise. Notice that $\Bbb E[X]=\Bbb E[X_2+\cdots+X_n]=\Bbb E[X_2]+\cdots+\Bbb E[X_n]$.
Let's try to figure out $\Bbb E[X_5]$. Observe that because of the way we defined it, $\Bbb E[X_5]$ is just the probability that $5$ is under $1$ in the tree. Based on your observation, this happens precisely when $1$ is inserted before any of $2,3,4,5$ is inserted, which happens with probability $\frac15$. Similarly, if you replace $5$ with $i$, you get $\Bbb E[X_i]=\frac1i$. So the desired value is $\frac12+\frac13+\cdots+\frac1n$.