The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

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.

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  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.

Hints

  • Hint 1
    How many possible triangles have their top tip on the root node?
  • Hint 2
    Could you then find an expression for the number of possible triangles with the top tip on a node at level \(k.\)
  • Hint 3
    How many nodes are there on level \(k?\)
  • Hint 4
    Try to express the sum of the triangles at each level into two sums, one of which is easier to calculate.
  • Hint 5
    To calculate the other sum, find a general expression in terms of \(x\) whose derivative has a similar form to our sum.
  • Hint 6
    You should find the general expression easier to simplify. Take the derivative of the simplified expression.
  • Hint 7
    Which value should \(x\) take so that we get the result of our sum?
  • Hint 8
    To find a recursive expression, think of how you could build the \((n+1)\)-level binary tree from the \(n\)-level binary tree.
  • Hint 9
    Have 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.foo[email protected]. Please do not write to this address regarding general admissions or course queries.