0
$\begingroup$

Learning induction proof now, found a "simple" example, which is a bit confusing to me (not sure if it is a valid example). If so, why the IH( suppose a root of rank k has at least $2^k$ vertices in its tree )is a valid one since it just repeating the statement that we are trying to prove ? What about the induction step?(Then a root ... in its tree.) enter image description here

How should we add more information to make easy to follow and more convincing?

$\endgroup$
  • 1
    $\begingroup$ Please do not include images containing text. All text should be included as such in the question; otherwise, it cannot be found using the site's search engine. Thank you. $\endgroup$ – dkaeae Dec 17 '18 at 10:26
1
$\begingroup$

This is a perfect example of a sloppily written induction proof. Of course the induction hypothesis is not only repeating the proof's statement; otherwise, it would not qualify as a proof at all since it would be assuming the statement is true regardless of the ensuing argument. What is meant, instead, is that $k$ is then fixed and the induction step is conducted for this particular choice of $k$.

The following proof structure is more elegant and IMO much easier to follow (esp. for beginners):

  • Induction basis: [...]
  • Induction step: let $k$ be given.
    Induction hypothesis (IH): let [statement you are trying to prove] be true for $k$.
    Then [ensuing reasoning which shows the statement is true for $k + 1$ by making use of IH].

This makes it explicit for which $k$ the hypothesis should hold as well as what statement it is exactly that we are trying to prove in the induction step.

$\endgroup$

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.