# Proof the number of expected node in a binary using mathematical induction

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.

• Are you familiar with linearity of expectation? Nov 27 '20 at 13:14
• no, I have not learnt about it
– Www
Nov 27 '20 at 13:21
• You will not be able to solve this without using linearity of expectation. Nov 27 '20 at 13:22
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$$.