ヒープデータ構造について


n 個の要素を持つヒープの、高さ h における節点が n/2^(h+1) 個である、理由がわかりません。

問題文の原文はこちらです：

> Show that there are at most ⌈n/2^(h+1)⌉ nodes of height h in any n-element
> heap.

以下がIntroduction to Algorithms 練習問題6.3-3に対するInstructor's Manual
の解説ですが、なぜh=0が正しいからの証明から始まるのか、また＃は何をさしているのかよくわかりません。

もしもっとわかりやすい証明があれば、解説をお願いします。

[![解説1](https://i.stack.imgur.com/xUiYq.png)](https://i.stack.imgur.com/xUiYq.png)

[![解説2](https://i.stack.imgur.com/HFepL.png)](https://i.stack.imgur.com/HFepL.png)




回答となると、この英文を訳すしかないので、解釈に必須の部分だけ書きますね。

この問題は[二分ヒープ](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83%97)を対象としていて、最深部以外は完全二分木になることが前提。上から各段のノードを数えると1,2,4,8...となりますが、最後の段は2の累乗になっているとは限りません。また"at
most"はつまり取りうる最大の数という意味なので、1からn/2^(h+1)の間の数ならOKです。

ある関数f(k)があったとして、k=0,1,2,3...とします。f(k+1)をf(k)で表すことができるとき、初期条件f(0)が決まれば、あとは再帰的に答えが正しいことが証明できます。それがh=0の証明から始める理由です。これを[数学的帰納法(mathematical
induction)](https://ja.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E7%9A%84%E5%B8%B0%E7%B4%8D%E6%B3%95)と言います。

**説明中に出てくる変数**

n: ツリー中の全ノード数  
h: height（高さ）はノードを下から辿った数  
d: depthまたはlevel（深さ）はノードをルートから辿った数  
H: ツリー全体の高さ  
x: 最深部のノードの数

**base caseのnが偶数xが奇数の説明**  
絵を描いてみました。下手くそですみません。  
[![画像の説明をここに入力](https://i.stack.imgur.com/jcQgw.png)](https://i.stack.imgur.com/jcQgw.png)

**他の証明方法?**

xを末端の葉の数とした時、nは次のように表せますし、高さは最低log(n+1)あることを手掛かりに展開するような方向でいけるかもしれません。

[![全ノードの定義](https://i.stack.imgur.com/bdjjK.png)](https://i.stack.imgur.com/bdjjK.png)




回答となると、この英文を訳すしかないので、解釈に必須の部分だけ書きますね。

この問題は[二分ヒープ](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83%97)を対象としていて、最深部以外は完全二分木になることが前提。上から各段のノードを数えると1,2,4,8...となりますが、最後の段は2の累乗になっているとは限りません。また"at
most"はつまり取りうる最大の数という意味なので、1からn/2^(h+1)の間の数ならOKです。

ある関数f(k)があったとして、k=0,1,2,3...とします。f(k+1)をf(k)で表すことができるとき、初期条件f(0)が決まれば、あとは再帰的に答えが正しいことが証明できます。それがh=0の証明から始める理由です。これを[数学的帰納法(mathematical
induction)](https://ja.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E7%9A%84%E5%B8%B0%E7%B4%8D%E6%B3%95)と言います。

**説明中に出てくる変数**

n: ツリー中の全ノード数  
h: height（高さ）はノードを下から辿った数  
d: depthまたはlevel（深さ）はノードをルートから辿った数  
H: ツリー全体の高さ  
x: 最深部のノードの数

**base caseのnが偶数xが奇数の説明**  
絵を描いてみました。下手くそですみません。  
[![画像の説明をここに入力](https://i.stack.imgur.com/jcQgw.png)](https://i.stack.imgur.com/jcQgw.png)

**他の証明方法?**

xを末端の葉の数とした時、nは次のように表せますし、高さは最低log(n+1)あることを手掛かりに展開するような方向でいけるかもしれません。

[![全ノードの定義](https://i.stack.imgur.com/bdjjK.png)](https://i.stack.imgur.com/bdjjK.png)

