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

 

[InteGrand]

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

 

[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?