question about strong induction (1 Viewer)

[oredbayz]

hey users,

just got a question about strong induction

for the assumption case, what would be the condition to assume n=<k or assume n=k, and what is the difference and would we lose marks for using wrong one?

also, would we ever need to assume/prove n=<k+1

thanks

 

[Drongoski]

Strong Induction: Hypothesis step: Assume true for n <= k

 

[CM_Tutor]

Or, if you need n cases in the assumption, you need to establish n cases in the first part.

For example, for the Fibonacci Sequence: F₁ = 1, F₂ = 1, F_n+2 = F_n + F_{n + 1} for all positive integers n. To prove the general formula for the nth term, you will need to assume the two preceding terms, so you will need to prove the general formula works for F₁ and for F₂ before making the assumption.

 

[oredbayz]

Strong Induction: Hypothesis step: Assume true for n <= k

why cant we just use n=k

 

[CM_Tutor]

Using n = k is ordinary induction. Strong induction is used in cases where ordinary induction doesn't work.

 

[stupid_girl]

These are different stronger versions of induction.

A.
The statement is true for n=1
If it is true for n=1,2......,k, then it is also true for n=k+1.

B.
The statement is true for n=1,2
If it is true for n=k,k+1, then it is also true for n=k+2.

 

[oredbayz]

These are different stronger versions of induction.

A.
The statement is true for n=1
If it is true for n=1,2......,k, then it is also true for n=k+1.

B.
The statement is true for n=1,2
If it is true for n=k,k+1, then it is also true for n=k+2.

so the second version is usually just recurrence induction

and the first version applies to all other scenarios? so inequalities, sequences etc?

 

[oredbayz]

how do we know when strong induction is needed? @CM_Tutor

 

[Trebla]

I am not sure that strong induction is actually in the syllabus anymore. I cannot see any explicit reference to it. Given it is a slightly conceptually different approach to normal induction, if a question does appear that requires it (highly unlikely), you will have to be hand-held in the steps.

 

[oredbayz]

I am not sure that strong induction is actually in the syllabus anymore. I cannot see any explicit reference to it. Given it is a slightly conceptually different approach to normal induction, if a question does appear that requires it (highly unlikely), you will have to be hand-held in the steps.

double 2 double O that's sweet so ill just ignore strong induction and hope for the best

 

[CM_Tutor]

The most obvious place for strong induction is a recurrence relation that depends on the preceding two terms.

It occurs to me that it could be asked as something like question 6(b) of the 1992 SGS 4u Trial paper, which I am posting below.



@Trebla, do you think asking in this form would be fair for the 2020-and-beyond MX2 syllabus?

 

[Trebla]

The most obvious place for strong induction is a recurrence relation that depends on the preceding two terms.

It occurs to me that it could be asked as something like question 6(b) of the 1992 SGS 4u Trial paper, which I am posting below.

View attachment 32920

@Trebla, do you think asking in this form would be fair for the 2020-and-beyond MX2 syllabus?

Possibly, with that level of hand-holding. It would still be highly unlikely to appear in a HSC exam though. Even in the old syllabus where strong induction was assessable, such questions were still quite rare in the HSC exams.