# Practice Paper 4 Question 11

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. What is the total number of triangles formed in this way? Give a recursive expression for this number.

## Related topics

## Warm-up Questions

- 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.

## Hints

- Hint 1How many possible triangles have their top tip on the root node?
- Hint 2Could you then find an expression for the number of possible triangles with the top tip on a node at level \(k.\)
- Hint 3How many nodes are there on level \(k?\)
- Hint 4Try to express the sum of the triangles at each level into two sums, one of which is easier to calculate.
- Hint 5To calculate the other sum, find a general expression in terms of \(x\) whose derivative has a similar form to our sum.
- Hint 6You should find the general expression easier to simplify. Take the derivative of the simplified expression.
- Hint 7Which value should \(x\) take so that we get the result of our sum?
- Hint 8To find a recursive expression, think of how you could build the \((n+1)\)-level binary tree from the \(n\)-level binary tree.
- Hint 9Have you tried building the 3-level binary tree from the 2-level binary tree?

## Solution

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.\)

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.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.[email protected]. Please do not write to this address regarding general admissions or course queries.