等比数列求和

2018-10-11 本文已影响14人 Paycation

已知深度为 1 的二叉树最多只有 1 个结点。深度为 2 最多有 2 + 1 = 3 个结点，深度为 3 最多有 4 + 2 + 1 = 7个结点，依次类推，深度为 k 的二叉树，最多多少个结点？
$\begin{aligned} &a_1=1,q=2\\ &a_2 = a_1q = 2^1\\ &a_3 = a_1q^2 = 2^2\\ &...\\ &a_n = a_1q^{n-1}=2^{n-1}\\ \end{aligned}$

观察下面两个式子：
$\begin{aligned} S_n&=a_1+a_2+...+a_n\\ &=a_1+a_1q+a_1q^2+...+a_1q^{n-1}\\ &\\ qS_n&=a_1q+a_1q^2+...+a_1q^{n-1}+a_1q^n\\ \end{aligned}$

所以 $qS_n - S_n = a_1q^n-a_1$ ，整理得：
$S_n = \dfrac{a_1(q^n-1)}{q-1}$
当 $a_1=1,q=2$ ，那么 $S_n = 2^n-1$ 。即深度为 n 的二叉树，最多 $2^n-1$ 个结点。

等比数列求和

猜你喜欢

热点阅读