3
$\begingroup$

CLRS asked it's readers to prove that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$ in any n-element heap as an exercise.
The principle of Mathematical Induction can be used to prove this as explained here.

My question is how one can come up with this formula at first place. Are there any key observations that lead us to this expression initially. And then proof by induction that this will hold true for all positive integer.

$\endgroup$
3
$\begingroup$

You use the principle of scientific induction: you try a few examples and guess a good bound, and then try to prove it. Simultaneously, you try to construct counterexamples. Sometimes your failed attempts at proving a bound help you find a counterexample refuting it.

Often in research one of the hardest steps is to come up with the correct conjectures. This is a creative endeavor and there are no rules which guarantee success. Skill and experience help, but sometimes you just need to be lucky.

$\endgroup$
  • $\begingroup$ So does that mean, finding a valid counter example will all it take to refute any such conjectures? $\endgroup$ – Prateek Mar 26 '16 at 16:07
  • 1
    $\begingroup$ @Prateek Right, true claims have no counterexamples. $\endgroup$ – Yuval Filmus Mar 26 '16 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.