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.

  1. Differentiate $y=x^n.$
  2. Evaluate the sum $\sum_{k=0}^{n}{2^k}.$ Note: This result is important in Computer Science.
  3. A geometric progression starts with $x, 2x^2, 4x^3, \ldots.$ Find the recursive formula of the sequence.

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.