question about strong induction (1 Viewer)

oredbayz

New Member
Joined
Oct 9, 2021
Messages
29
Gender
Male
HSC
2021
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

Well-Known Member
Joined
Feb 22, 2009
Messages
4,238
Gender
Male
HSC
N/A
Strong Induction: Hypothesis step: Assume true for n <= k
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
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: F1 = 1, F2 = 1, Fn+2 = Fn + Fn + 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 F1 and for F2 before making the assumption.
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
Using n = k is ordinary induction. Strong induction is used in cases where ordinary induction doesn't work.
 

stupid_girl

Active Member
Joined
Dec 6, 2009
Messages
221
Gender
Undisclosed
HSC
N/A
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

New Member
Joined
Oct 9, 2021
Messages
29
Gender
Male
HSC
2021
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?
 

Trebla

Administrator
Administrator
Joined
Feb 16, 2005
Messages
8,113
Gender
Male
HSC
2006
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

New Member
Joined
Oct 9, 2021
Messages
29
Gender
Male
HSC
2021
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

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
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.

SGS 1992 4u Trial q6(b).png

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

Trebla

Administrator
Administrator
Joined
Feb 16, 2005
Messages
8,113
Gender
Male
HSC
2006
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.
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top