Show that there are at most \(\lceil n / 2^{h+1} \rceil\) nodes of height \(h\) in any \(n\)-element heap.

Exercise 6.1-7 showed that the leaves of an \(n\)-element heap are indexed by \(\lfloor n / 2 \rfloor + 1, \lfloor n / 2 \rfloor + 2, \dots, n\). These elements correspond to half of the heap array plus the middle element if there is one. Thus, we know an \(n\)-element heap has \(\lceil n / 2 \rceil\) leaf nodes, or nodes at height \(h = 0\). This forms the base case for a proof by induction because at height \(h = 0\), our claim states that there are at most \(\lceil n / 2^{0+1} \rceil = \lceil n / 2 \rceil\) nodes.

In order to show that this claim holds for \(n + 1\), suppose we modify the heap by removing all leaf nodes. Our new heap now has \(n - \lceil n / 2 \rceil\) nodes. Because \(n\) is an integer, \(n - \lceil n / 2 \rceil = \lceil n - n / 2 \rceil = \lfloor n / 2 \rfloor\). Our claim states that there are now \(\left\lceil \frac{\lfloor n / 2 \rfloor}{2^{0+1}} \right\rceil\) nodes at height \(h = 0\). Based on the conclusions of Exercise 6.1-7, an \(\lfloor n / 2 \rfloor\) - element heap has \(\left\lceil \frac{\lfloor n / 2 \rfloor}{2^{0+1}} \right\rceil = \lceil \lfloor n / 4 \rfloor \rceil = \lfloor n / 4 \rfloor\) leaf nodes and so we see that this claim holds for all values of \(h\) and \(n\).