I'm currently studying a proof in graph theory and it says:
'Suppose that what we want to prove is true for 1,2,3, ..., n-1. We will prove that it holds for n'. Is this a legit form of induction?
Usually, in the induction proofs I encountered until now it was something like. Suppose it's true for n, then we will prove it's true for n +1 or suppose it's true for n-1, we will prove that it's true for n but this seems to be another form induction than the one mentioned above.
Thanks for any help.
Answer
Yes. It is called complete induction. From Wikipedia:
Another variant, called complete induction, course of values induction or strong induction (in contrast to which the basic form of induction is sometimes known as weak induction) makes the inductive step easier to prove by using a stronger hypothesis: one proves the statement $P(m+1)$ under the assumption that $P(n)$ holds for all natural $n$ less than $m+1$; by contrast, the basic form only assumes $P(m)$.
No comments:
Post a Comment