“However, it is very important that the uncertainty in the number of trials is taken into account because over-estimating a fraction is a costly mistake.“
Seems fairly clear to me that you’re supposed to use a lower bound estimate to take into account variance on the fraction due to the number of trials in a way to bounds the chance of over estimation.
Further, there is no need for a heuristic when there a several statistical models for this exact problem with clear properties. Some are given in the answer.