In: Advanced Math
If you prove by strong induction a statement of the form ∀ n ≥ 1P(n), the inductive step proves the following implications (multiple correct answers are possible):
a) (P(1) ∧ P(2)) => P(3)
b) (P(1) ∧ P(2) ∧ P(3)) => P(4)
c) P(1) => P(2)
To answer this first we have to know the difference between general induction and strong induction .
In general induction , we prove the induction step that is to
prove the statement for
we have the induction hypothesis the statement is true for
.
While in strong induction we prove the induction step
that is to prove the statement for
we have the induction hypothesis the statement is true for
,
or more values of
That is if we assume that the statement is true
for
to prove that the statement is true for
then it is general induction and if we assume more values of
to prove that the statement is true for
then it will be strong induction .
Hence ,
is strong induction .
is strong induction .
is not strong induction .
Answer :
and
.
.
.
.
If you have any doubt please comment .