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!