嚴格二叉樹中的樹葉數量

我在尋找派生我們如何得出以下結果。嚴格二叉樹中的樹葉數量

2與i的冪的和，因爲我從0到n =>答案給出爲（2（n + 1）-1的冪）。

任何人都可以告訴我我們如何達到上述結果或解決方案的適當鏈接。

謝謝！

感應證明：對於n = 0，2^0 = 1 = 2^1 - 1。假設對於n = k-1，2^0 + ... + 2^k = 2^0 + ... + 2 ^（k-1）+ 2^k =（2^k-1）+ 2^k = 2 * 2^k-1 = 2 ^（k + 1）-1。 –

實際上這是節點的數量，而不是葉子 –

證明是用歸納。

觀察它是對於n =真0 - sum0-> 0 = 1 = 2^1 - 1

假設爲真N = k-1個，所以總結[0-> K-1] = 2^k = 1 然後，sum [0-> k] = sum [0-> k-1] + 2^k = 2^k-1 + 2^k = 2（2^k）-1 = 2^k + 1） - 1.

因此對所有的n都是正確的。

2011-08-08 12:20:16 Chowlett

如果你想更清楚的（更直觀的）的解釋，你可以閱讀this nice explanation

2011-08-08 12:18:28 Fezvez

回答