Facts about internal and external path lengths of binary tree
I'm assuming the following model for a binary search tree of size $n$. Consider the following infinite process. At step 0, we have the empty tree. At step 1, we have the tree having some arbitrary value at the root. At step $m&gt;1$, if the current (ordered) contents of the tree at the previous step are $x_1&lt;\ldots&lt;x_{m-1}$, we choose an interval uniformly at random among the $m$ intervals
$$(-\infty,x_1),(x_1,x_2),\ldots,(x_{m-2},x_{m-1}),(x_{m-1},\infty),$$
choose an arbitrary element from the interval, and insert it to the binary tree. A random binary search tree of size $n$ is obtained by stopping this process at step $n$, and erasing the values at the vertices.

You can show that the arbitrary choices do not affect the distribution. Also, the relative order of the elements of the tree at step $n$ (in order of insertion) is a random permutation on $n$ elements.

You haven't explained what you mean by $S_n$ and $U_n$ exactly, so I assume you are using the following definitions:


Let $T_n$ be a random binary search tree of size $n$ before erasing the values. Choose one of the $n$ elements at random, and run binary search on $T_n$ and this element. The average number of comparisons in this process is $S_n$.
Let $T_n$  be a random binary search tree of size $n$ before erasing the values, and let $x$ be the random element inserted by the process at the following step. Run binary search on $T_n$ and $x$. The average number of comparisons in this process is $U_n$.


First fact

Given these definitions, the first fact is easy to prove. Suppose that the element we search for was inserted at step $i$. Note that the distribution of $i$ is uniform over $\{1,\ldots,n\}$. Inserting $i$ at step $i$ requires $U_i$ comparisons in expectation. It takes us the same number of steps to reach this element at the current experiment, and one more comparison to verify that we have indeed found the element. The formula follows.

Second fact

Here we need a non-trivial argument, outlined in the Wikipedia article. Let the sorted elements in the tree be $x_1&lt;\cdots&lt;x_n$. Suppose that the element we look for is $x_i$. The search goes through an element $x_j$ if $x_j$ is an ancestor of $x_i$. Thus, given $i$, the average number of comparisons is $$\sum_{j=1}^n \Pr[\text{$x_j$ is an ancestor of $x_i$}].$$ Now $x_j$ is an ancestor of $x_i$ if among all elements in $\{x_i,\ldots,x_j\}$ (or $\{x_j,\ldots,x_i\}$), $x_j$ was the first inserted. Since the true order of insertion is a random permutation of $x_1,\ldots,x_n$, we conclude that $$\Pr[\text{$x_j$ is an ancestor of $x_i$}] = \frac{1}{|i-j|+1}.$$ Choosing a random $i$, this shows that
$$
\begin{align*}
S_n &amp;= \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^n \frac{1}{|i-j|+1} \\ &amp;=
\frac{1}{n} \sum_{i=1}^n \frac{1}{|i-i|+1} + \frac{2}{n}\sum_{i=1}^n\sum_{j=1}^{i-1} \frac{1}{i-j+1} \\ &amp;=
1 + \frac{2}{n}\sum_{i=1}^n \sum_{j=2}^i \frac{1}{j} \\ &amp;=
1 + \frac{2}{n}\sum_{i=1}^n (H_i - 1) \\ &amp;=
\frac{2}{n} \sum_{i=1}^n H_i - 1 \\ &amp;=
\frac{2(n+1)}{n} (H_{n+1} - 1) - 1.
\end{align*}
$$ 
Here $H_i$ is the $i$th harmonic number, and we used the identity $\sum_{i=1}^n H_i = (n+1)(H_{n+1}-1)$. It is well-known that $H_i = \ln i + \gamma + O(1/i)$ and that $\ln (n+1) = \ln n + O(1/n)$, and so
$$
\begin{align*}
S_n &amp;= 2\left(1+\frac{1}{n}\right) (\ln n + \gamma - 1 + O(1/n)) - 1 \\ &amp;=
2\ln n + 2\gamma - 3 + \frac{2\ln n}{n} + O\left(\frac{1}{n}\right).
\end{align*}
$$

Third fact

The upper bound is given by a path, in which case $I_n = 0 + 1 + \cdots + (n-1) = n(n-1)/2$. For the lower bound, it is easier to consider first the special case $n = 2^m-1$. In that case, the lower bound is given by a balanced binary tree. Such a tree has $2^k$ nodes at depth $k$, and so
$$
I_n = \sum_{d=0}^{m-1} 2^k k = 2^m (m-2) + 2 = (n+1)\log_2 \tfrac{n+1}{4} + 2.
$$
More generally, if $n = 2^m-1+x$ for $x &lt; 2^m$, it is best to put the $x$ extra nodes at depth $m$, and so
$$
\begin{align*}
I_n &amp;= 2^m(m-2) + 2 + mx \\ &amp;= (m-2)(2^m+x) + 2(x+1) \\ &amp;= (m-2)n + m-2 + 2(x+1).
\end{align*}
$$
Notice that $m \leq \log_2 (n+1) &lt; m+1$, that is, $m = \lfloor \log_2 (n+1) \rfloor$. Therefore
$$
I_n = n\lfloor \log_2 (n+1) \rfloor + O(n) = n \log_2 n + O(n).
$$
To get an actual lower bound, notice that
$$
I_n \geq (m-2)n + m &gt; n \log_2 \frac{n+1}{4} \geq n\log_2 \frac{n}{4}.
$$