I'm looking for a mathematical proof that shows there are at most
n/(2^(h+1)) vertices of height h in an n-element heap.

Hello Cminardua,

I found two references that describe a proof for this problem:
  http://web.njit.edu/~calvin/class/dl435/sol3.pdf
  http://web.njit.edu/~kks2/Courses/CIS%20435/CIS435Files/week4.pdf
Both appear to be the results of homework submitted for a course at
the New Jersey Institute of Technology.

The proof is pretty straight forward, solving for height zero (the
bottom of the heap) and then using induction for all heights greater
than zero. The proof is also divided into two portions, based on an
odd or even number of nodes at the lowest level of the tree.

I found this solution by searching using phrases such as
  proof heap height
  proof heap height 6.3-3
and similar phrases.

If some part of the proof is unclear (another site indicates the proof
is "hard"), please use a clarification request. I would be glad to
walk through an example or two as needed.

  --Maniac