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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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