Average number of full nodes in a binary search tree
As the both the formula itself is given $f(n) = \frac{n-2}{3}$ as well as the inductive structure $f(n) = \frac{n-2}{n} + \frac1n \sum_{i=0}^{n-1}{\dots}$, it seems you are requested to show the formula by (mathematical) induction. Hint (2) only explains the formula.

Inductively you apply the formula for $f(k), k&lt;n$ in the recursive expression and conclude that it also holds for $f(n)$. I can do that, but run into trouble. The formulas do not match.

Summing $f(i) + f(n-i-1)$ is easy, as it is equal to $\frac{i-2}3 + \frac{n-i-1-2}3 = \frac{n-5}3$, so the $i$'s cancel. Plugging it into the recursion yields $\frac{n-2}{n} + \frac nn \frac{n-5}3$ which is not the expected $\frac{n-2}{3}$. 

edit: The first values of $f$ however are special. $f(0) = f(1) = 0$, where the formule $\frac {n-2}3$ predicts $\frac {-2}3$ and $\frac {-1}3$ respectively.  Thus we have to correct this within the summation, twice as it occurs in both $i=0,1$ and $i=n-1,n$, and add $\frac 2n$. Amazingly, that works.

Part (3) just expects you to know what is the relation between the numbers of full nodes and leaves in a binary tree.