Second Principle of Induction. (1 Viewer)

[Drsoccerball]

Vat... How does this even work ?



Also how would we even use this...

 

[leehuan]

I was going to suggest strong induction but then I realised n≥k

But if it holds for all n≥k then technically must it hold for n=k+1 anyway?

 

[Drsoccerball]

I was going to suggest strong induction but then I realised n≥k

But if it holds for all n≥k then technically must it hold for n=k+1 anyway?

It's not saying it holds for n>=k its just saying that n>=k.

 

[leehuan]

It's not saying it holds for n>=k its just saying that n>=k.

You lost me. Looks like a redundancy

 

[leehuan]

http://www.oxfordmathcenter.com/drupal7/node/114

You just typed it wrong. It's n≤k. Which means that this is just strong induction

 

[seanieg89]

Note that "strong" induction is a bit of a misnomer, regular induction is exactly as strong in the sense that assuming the "principle/axiom of induction" allows you to prove the "principle/axiom of strong induction".

To see this let S(n) be a sequence of propositions about positive integers and let T(n) be the statement that S(k) is true for all positive integers less than or equal to n. Then applying strong induction to the S sequence is the same as applying regular induction to the T sequence.

A standard application of strong induction is to show that every positive integer can be factorised into primes. (Strong induction does NOT give you the uniqueness of factorisation, and you need to do more work to get this.)

 

[tywebb]

(with correction)

See if you can understand (or even agree) with the following statement regarding strong induction:

The base step "the statement holds for n=1" is redundant (i.e., is not needed), in strong induction.

What you are describing is actually transfinite induction:

Showing that if the statement holds for all n < m then the same statement also holds for n = m.

Strictly speaking, it is not necessary in transfinite induction to prove the basis, because it is a vacuous special case of the proposition that if P is true of all n < m, then P is true of m. It is vacuously true precisely because there are no values of n < m that could serve as counterexamples.

See https://en.wikipedia.org/wiki/Mathematical_induction#Transfinite_induction

I doubt if many teachers would teach induction at this level.

 

[InteGrand]

Would you lose marks in the HSC if you didn't prove the base case (if using transfinite induction)?

 

[tywebb]

I'm pretty certain that most teachers would teach strong induction with including the base step too - even when they don't have to.

Many teachers just look puzzled when you say to them you don't need the base step in transfinite induction - because they don't understand it properly themselves.

Some of these teachers end up marking the HSC and may penalise for not including the basis step - even for transfinite induction.

So the advice some teachers will give is to include the base step - even in transfinite induction - even when you don't need it - just to ensure you don't lose marks.

This is a case where bad mathematics creeps into the HSC just to get marks (or to prevent losing them).

 

[InteGrand]

Speaking of induction in the HSC, it is common for students to write a sort of mantra at the end of induction proofs in the HSC (or at least was common before, not sure if it still is). Basically an explanation of why induction works or something iirc. I think such a mantra is no longer needed in the HSC, so why is it / was it common for students to do? Was it once required in the HSC?

 

[tywebb]

Speaking of induction in the HSC, it is common for students to write a sort of mantra at the end of induction proofs in the HSC (or at least was common before, not sure if it still is). Basically an explanation of why induction works or something iirc. I think such a mantra is no longer needed in the HSC, so why is it / was it common for students to do? Was it once required in the HSC?

It was never in the syllabus and hence was never required in the exams.

Nevertheless it is in many textbooks and many teachers who blindly teach from textbooks without any proper understanding about the subject they are teaching - led to the mantra being forced onto students by teachers who didn't have clue about what they were teaching.

The matter has been cleared up a few years ago at the HSC Feedback days and so the phenomenon is less prevalent thesedays - but alas hasn't completely disappeared, as it is still present in some textbooks and many teachers still blindly teach from textbooks.