Difficulty understanding the solution of heap problem in CLRS book? I am reading the solution of this problem in CLRS:

Show that there are at most $\lceil {n/2^{h+1}} \rceil$ nodes of height $h$ in any $n$-element heap.
Solution: All the nodes of height $h$ partition the set of leaves into sets of size between $2^{h-1}$ and $2^h$, where all but one is size $2^h$. Just by putting all the children of each in their own part of the partition. Recal from 6.1-2 that the heap has height $\lfloor\lg(n)\rfloor$, so, by looking at the one element of this height (the root), we get that there are at most $2^{\lfloor\lg(n)\rfloor}$ leaves. Since each of the vertices of height $h$ partitions this into parts of size at least $2^{h-1}+1$, and all but one corresponds to a part of size $2^h$, we can let $k$ denote the quantity we wish to bound,  so,
$$(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$$
so
$$k\leq \frac{n+2^h}{2^{h+1}+2^h+1} \leq \frac{n}{2^{h+1}}\leq \left\lceil\frac{n}{2^{h+1}}\right\rceil$$

But I don't understand how to come up with the fact that $(k-1)2^h + k(2^{h-1} + 1)$ is less than the number of leaves.
But I don't understand the how to come up with the fact that $(k−1)2^h+k(2^{h−1}+1)$ is less than the number of leaves.


It is quite straightforward from the very first statement of the solution which says there are all but one set of size $2^{h}$. Where $k$ is total number of sets of nodes at height $h$.

Therefore, total number of nodes at $h$ height is:
$$\begin{align*}
s &amp;= (\text{total sets} \times \text{size of each sets})\\
 &amp;= k(2^{h}+2^{h-1}+1)-1 \cdot 2^{h}\\
 &amp;= (k−1)2^h+k(2^{h−1}+1)
\end{align*}$$



Another way to solve this is here.