How to analyze the worst case of weighted quick-union method on union-find
This is just a note for myself in the future, in case anyone else out their ends up getting stumped by this problem. This answer expands off of @Apass.Jack's answer.

To prove that each level has a binomial coefficient, we use induction.
The base case of $n=1$ is ${1 \choose 0}$ is 1. $n$ represents the height of the nodes while the $0$ is just an arbitrary level of the tree.
Now, assume that at each level the number of nodes is ${n \choose i}$ where $0 \le i &lt; n$ for a tree $T_n$. When we combine 2 trees of size $2^n$ (let's call them $T_1$ or $T_2$), then one of them is chosen to point to the root and the other is chosen to become the root. Let's say that the root of $T_1$ is chosen to point to $T_2$. If this is the case, the depth of each nodes increases by 1. That means, in a sense, each node is "pushed" down the tree to the next level below. Now, if, by the inductive hypothesis, we have ${n \choose i}$ nodes at each level of $T_2$. However, for each level $i$ in the $T_1$, the number of nodes at is equivalent to the previous level in $T_1$, $i-1$. Therefore, for each level $i$ in $T_1$ connected to $T_2$, the number of nodes is ${n \choose i-1}$. So, if we count the number of nodes on each level, it's just the sum of the number of nodes at each level of $T_2$ and then the number of nodes at each level of $T_1$ connected to $T_2$. So, the number of nodes is ${n \choose i} + {n \choose i-1} = {n+1 \choose i}$. This fits the form of the inductive hypothesis; therefore it is proven.