2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

It's also called strong induction. Notice this is perfectly fine. The idea is that since if the $n-1$ case were proved, it required proving the $n-2$ case which required proving the $n-3$ case, etc... all the way down to your base case, which you proved. You're just taking advantage of all your information.

$\endgroup$
1
$\begingroup$

The induction is used to prove that

$$(\forall n\geq n_0)\;\;\; P_n$$

first, we check $P_{n_0}$.

secondly,

weak induction

we say:

Let $n\geq n_0\;\;:\: P_n$

and we prove $P_{n+1}.$

strong induction

we say:

let $n\geq n_0\;\;: P_{n_0};P_{n_0+1},...P_n$

and we prove $P_{n+1}$.

$\endgroup$
0
$\begingroup$

Yes, it is very corect. For example, view https://nrich.maths.org/4718. Good luck!

$\endgroup$

Your Answer

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