用归纳法推导：
1、height = 0时，成立，其level 0的节点个数为C(0,0)=1.
height = 1时，成立，其level 0的节点个数为C(1,0)=1，其level 1的节点个数为C(1,1)=1.
2、假设height = n-1时，每个level的节点个数都是二次项系数。
3、则height = n时，其是由两个height=n-1且节点个数符合二次项系数的tree组合而成的。
故其level 0的节点个数为1，符合C(n,0). 其level n的节点个数为1，符合C(n,n).
对level k（1 <= k <= n-1），其节点个数nodenumber = C(n-1,k) + C(n-1,k-1) = C(n,k)。
最后，原命题得证。
N = 2^n时，因为2^n = (1+1)^n = C(0,n) + C(1,n) + ……+ C(n,n)，根据上述命题，可知这个树是height=n，各层节点数是二次项系数的worst-case tree for weighted quick-union。
所以平均深度为depthaverage=（0* C(0,n) + 1*C(1,n) + ……+ n*C(n,n)）/ 2^n
根据r*C(r,n)=n*C(r-1,n-1)，上述公式化简为n *（C(0,n-1) + ……+C(n-1,n-1)）/ 2^n = n * 2^(n-1) / 2^n = n/2