1
$\begingroup$

The following algorithm constructs a binary tree.

MakeArray(array[x:y]) (
 if(x==y):
  the root is x
 else: 
  pick a number r as root
  MakeArray(array[x:r-1])
  MakeArray(array[r+1:y])
)

Let $a_n$ be the expected number of nodes which have two children in the tree with $n$ nodes generated.

Prove $a_n = \frac{n-2}{n}+\frac{1}{n}\sum_{i=0}^{n-1}(a_{i}+a_{n-i-1})$ using mathematical induction.

I have no idea where to start as I don't even know how to construct a proper equation to carry on the proof. Any help is appreciated.

$\endgroup$
6
  • $\begingroup$ Are you familiar with linearity of expectation? $\endgroup$ Nov 27 '20 at 13:14
  • $\begingroup$ no, I have not learnt about it $\endgroup$
    – Www
    Nov 27 '20 at 13:21
  • $\begingroup$ You will not be able to solve this without using linearity of expectation. $\endgroup$ Nov 27 '20 at 13:22
  • $\begingroup$ I just googled. geeksforgeeks.org/linearity-of-expectation $\endgroup$
    – Www
    Nov 27 '20 at 13:22
  • $\begingroup$ I am not sure how I can apply to this question $\endgroup$
    – Www
    Nov 27 '20 at 13:25
1
$\begingroup$

If the array has length $n = 1$ then the constructed tree consists just of a root. Therefore $a_1 = 0$. Similarly, $a_0 = 0$ (this is a corner case).

Now suppose that $n \geq 2$. Without loss of generality, assume that $x = 1$, and so $y = n$. The array splits into two halves: $1,\ldots,r-1$ and $r+1,\ldots,n$. The first has length $r-1$, and the second has length $n-r$. If $r = 1$ or $r = n$, the one of these halves is empty; this happens with probability $\frac{2}{n}$. So with probability $\frac{n-2}{n}$, the root has two children. Defining $i = r-1$, we see that $i$ is chosen uniformly among the $n$ options $0,\ldots,n-1$, and the two subarrays have lengths $i,n-1-i$. From here it is straightforward to deduce your formula, using linearity of expectation.

Your formula simplifies to $$ a_n = \frac{n-2}{n} + \frac{2}{n} \sum_{i=0}^{n-1} a_i. $$ This implies that $$ (n+1)a_{n+1} - na_n = n-1 + 2 \sum_{i=0}^n a_i - (n-2) - 2 \sum_{i=0}^{n-1} a_i = 1 + 2a_n, $$ and so $$ a_{n+1} = \frac{n+2}{n+1} a_n + \frac{1}{n+1} \Longrightarrow a_{n+1} - a_n = \frac{a_n}{n+1} + \frac{1}{n+1}. $$ Now \begin{multline} a_{n+2} - a_{n+1} = \frac{a_{n+1}}{n+2} + \frac{1}{n+2} = \frac{a_n}{n+1} + \frac{1}{(n+1)(n+2)} + \frac{1}{n+2} =\\ \frac{a_n}{n+1} + \frac{1}{n+1} = a_{n+1} - a_n. \end{multline} In other words, $a_n$ is an arithmetic progression. You can check that $a_n = \frac{n-2}{3}$ for $n \geq 2$.

$\endgroup$

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.