Thread: Binary Tree Question

Hello Math Help Forum! This is my first post. See, I have a final tomorrow and have greatly procrastinated on studying. The professor gave a practice final and I missed all of the solutions, and I do not understand how to solve the following question:

Let T be the full binary tree with height n with 2^n terminal vertices. Let r denote the root. Define a weight on the edges of T as follows: If an edge e connects a vertex with its left child, define w(e)=0. If an edge connects a vertex with its right child, define w(e)=1. Now let P be the set of simple paths from r to the terminal vertices. Note that |P| = 2^n since there is one simple path from r to each terminal vertex. Let P(k) be the set of paths in P with total weight k. Show |P(3)|<= n^3.

(Recall that the weight of a path is the sum of weights of the edges in the path).

My first instinct was induction but that didn't work. My next was a recurrence relation but I got lost. Any tips?? Thanks!

Isn't it true that ?

Just an aside: this depends on a couple of definitions, as height is sometimes defined as 0 for a tree of size (node count) 1, but other times is defined as 1 for a tree of size 1 (if the order zero graph is allowed, which is extremely useful for setting up the recursive structure of the binary tree in computer science). Based on your formula it seems you're using the former definition.

This problem is essentially asking "in a full tree of n+1 levels, prove there are at most n^3 paths from root to leaf that branch right exactly three times". You will get n branch choices, one choice for each level indexed from 1 to n. You have to choose exactly three of these to head to the right. So emakarov is correct.

(This seems like a very silly question. I'm not sure what content area they are trying to assess here outside of basic logic.)