Is this a valid induction proof example ?

Question

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.)

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

Answer 1

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.