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$ Commented Nov 27, 2020 at 13:14
  • $\begingroup$ no, I have not learnt about it $\endgroup$
    – Www
    Commented Nov 27, 2020 at 13:21
  • $\begingroup$ You will not be able to solve this without using linearity of expectation. $\endgroup$ Commented Nov 27, 2020 at 13:22
  • $\begingroup$ I just googled. geeksforgeeks.org/linearity-of-expectation $\endgroup$
    – Www
    Commented Nov 27, 2020 at 13:22
  • $\begingroup$ I am not sure how I can apply to this question $\endgroup$
    – Www
    Commented Nov 27, 2020 at 13:25

1 Answer 1

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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.