You have a binary tree with $n$ levels similar to the figure shown. On each level you draw a line passing through all nodes on that level. (a) What is the total number of triangles formed in this way? (b) Give a recursive expression for this number.
-
- Differentiate
$y=x^n.$ - Evaluate the sum
$\sum_{k=0}^{n}{2^k}.$Note: This result is important in Computer Science. - A geometric progression starts with
$x, 2x^2, 4x^3, \ldots.$Find the recursive formula of the sequence.
- Differentiate
-
How many possible triangles have their top tip on the root node?
-
Could you then find an expression for the number of possible triangles with the top tip on a node at level
$k.$ -
How many nodes are there on level
$k?$ -
Try to express the sum of the triangles at each level into two sums, one of which is easier to calculate.
-
To calculate the other sum, find a general expression in terms of
$x$whose derivative has a similar form to our sum. -
You should find the general expression easier to simplify. Take the derivative of the simplified expression.
-
Which value should
$x$take so that we get the result of our sum? -
To find a recursive expression, think of how you could build the
$(n+1)$-level binary tree from the$n$-level binary tree. -
Have you tried building the 3-level binary tree from the 2-level binary tree?
-
(a) Every node at level
$k$has$n-k$possible triangles with the top tip on that node. There are$2^{k-1}$nodes at level$k$. Hence$t_n=\sum_{k=1}^{n-1} (n-k)2^{k-1}=n(2^{n-1}-1)-\sum_{k=1}^{n-1}k2^{k-1}.$This last sum can be solved by differentiating for$\sum_k x^k$and substitute$x=2.$We get$t_n=n2^{n-1}-n-n2^{n-1}+2^n-1=2^n-n-1.$(b) To work out a recursive expression for this, realise that we can build the
$(n+1)$-level binary tree (with horizontal lines) from the$n$-level one by making another copy horizontally, and then adding a root node at the top. Copying the existing tree would double the number of existing triangles, and then adding a root node at the top adds$n$new triangles that didn’t exist before. Hence$t_{n+1} = 2t_n + n.$Alternatively we can subtract consecutive terms to get
$t_{n+1} = t_n + 2^n - 1.$Note: It’s also possible to figure out the answer by progressive trials and then prove it by induction.