[解決済み] Max-Heapifyの最悪のケース - 2n/3を得るには？

質問

CLRS第3版の155ページに、MAX-HEAPIFYではと記載されています。

子のサブツリーのサイズはそれぞれ最大で 2n/3 -最悪の場合 最悪のケースは、木の最下層がちょうど半分になったときに起こります。

最下層がちょうど半分のときに最悪になる理由はわかりました。そして、それはこの質問でも回答されています。 MAX-HEAPIFYにおける最悪のケース: "最悪のケースは、ツリーの一番下のレベルがちょうど半分のときに発生します"。

私の質問は、2n/3を取得する方法ですか？

なぜ最下層が半分になると、子木の大きさは2n/3までなのでしょうか？

どのように計算するのですか？

ありがとうございます。

どのように解決するのですか？

説明：高さhのノードの数は2^hであり、幾何級数の和の公式によって（高さ0からh-1までのノードの和）+1に等しく、高さ0からh-1までのすべてのノードは正確に2つの子を持つノードである}。

    ROOT
  L      R
 / \    / \
/   \  /   \
-----  -----
*****

Rのノード数をkとすると、Lのノード数はk + (k + 1) = 2k + 1となる。ノードの総数は、n = 1 + (2k + 1) + k = 3k + 2 (ルート + L + R)です。比率は(2k + 1)/(3k + 2)であり、これは上で2/3に束縛されている。kが無限大になるときの極限は2/3なので、2/3より小さい定数は働きません。