《数据结构（C语言版）》p282证明

∑ j = 1 h − 1 2 h − j ∙ j ≤ ( 2 n ) ∑ j = 1 h − 1 j / 2 j ≤ 4 n sum_{j=1}^{h-1}2^{h-j} bullet j leq(2n)sum_{j=1}^{h-1} j/2^j leq 4n j=1∑h−1​2h−j∙j≤(2n)j=1∑h−1​j/2j≤4n
先证明左侧，首先通过二叉树的性质可以得出，若二叉树的高度为h，节点个数为n，则
2 h − 1 ≤ n ≤ 2 h − 1 2^{h-1} leq n leq 2^h-1 2h−1≤n≤2h−1
最多的情况下二叉树是满二叉树，第1层1个节点，第2层2个，第3层4个…，由等比数列的前n项和，可得出
n = 2 h − 1 n = 2^h-1 n=2h−1
最少的情况下第 1 层到第 h - 1 层构成满二叉树，第h层只有一个节点，此时
n = 2 h − 1 − 1 + 1 = 2 h − 1 n=2^{h-1}-1+1=2^{h-1} n=2h−1−1+1=2h−1
因此有
2 h ≤ 2 n 2^h leq 2n 2h≤2n
代入左侧
∑ j = 1 h − 1 2 h − j ∙ j ≤ 2 h ∑ j = 1 h − 1 j / 2 j ≤ ( 2 n ) ∑ j = 1 h − 1 j / 2 j sum_{j=1}^{h-1}2^{h-j} bullet j leq 2^h sum_{j=1}^{h-1} j/2^j leq(2n) sum_{j=1}^{h-1} j/2^j j=1∑h−1​2h−j∙j≤2hj=1∑h−1​j/2j≤(2n)j=1∑h−1​j/2j
再来看右侧，
∑ j = 1 h − 1 j / 2 j = 1 2 + 2 2 2 + ⋯ + h − 1 2 h − 1 sum_{j=1}^{h-1} j/2^j = frac{1}{2}+frac{2}{2^2}+ cdots+frac{h-1}{2^{h-1}} j=1∑h−1​j/2j=21​+222​+⋯+2h−1h−1​
S = 1 2 + 2 2 2 + 3 2 3 + ⋯ + h − 1 2 h − 1 S=frac{1}{2}+frac{2}{2^2}+frac{3}{2^3} + cdots+frac{h-1}{2^{h-1}} S=21​+222​+233​+⋯+2h−1h−1​
2 S = 1 + 2 2 + 3 2 2 + 4 2 3 + ⋯ + h − 1 2 h − 2 2S=1+frac{2}{2}+ frac{3}{2^2}+frac{4}{2^3}+cdots+frac{h-1}{2^{h-2}} 2S=1+22​+223​+234​+⋯+2h−2h−1​
由 2 S − S 得 ， S = 2 − 1 2 + 1 2 2 + 1 2 3 + ⋯ + 1 2 h − 2 − h − 1 2 h − 1 由2S-S得， S=2-frac{1}{2}+frac{1}{2^2}+frac{1}{2^3}+cdots+frac{1}{2^{h-2}}-frac{h-1}{2^{h-1}} 由2S−S得，S=2−21​+221​+231​+⋯+2h−21​−2h−1h−1​
通过等比数列求和公式，可得
S = 2 − 1 2 h − 2 − h − 1 2 h − 1 S=2-frac{1}{2^{h-2}}-frac{h-1}{2^{h-1}} S=2−2h−21​−2h−1h−1​
lim ⁡ h → + ∞ 2 − 1 2 h − 2 − h − 1 2 h − 1 = 2 lim_{h to +infty }2-frac{1}{2^{h-2}}-frac{h-1}{2^{h-1}}=2 h→+∞lim​2−2h−21​−2h−1h−1​=2
因此，右侧成立。