等比数列和 详细证明过程

问题分析计算满二叉树高度

问题

等比数列定义如下： a1 = x^0 = 1 a2 = x^1 … an = x^(n-1)

求S(n) = a1 + a2 + … + an

分析

研究变量S(n)、S(n-1)与等比数列的关系，很明显 S(n) - S(n-1) = an

但2个变量需要两条式子才能解出来，那就从等比数列的特性入手 x * S(n-1) =x+x * x+x * x * x +…+x^(n-1) = S(n) - 1 即 S(n) = x * S(n-1) + 1

计算

所以2条式子为：

S(n) - S(n-1) = anS(n) = x * S(n-1) + 1

消去S(n-1),得到

S(n) = (x^n - 1) / (x - 1)

满二叉树高度

满二叉树：x = 2，a(n)为第n(n=1,2…)行数列，则总结点数为：

S(n) = a1 + a2 +… + a(n) = 2^n - 1

由于单节点时树的高度为0，即height = n - 1 所以

height = n - 1 = log(S(n) + 1) - 1 设总结点数为N，则height = log2(N-1) - 1