Cambridge strong induction (1 Viewer)

mr.habibbi

Member
Joined
Oct 27, 2019
Messages
41
Gender
Male
HSC
2021
Hi all,

Need help with 'strong' induction, a few questions on this topic in cambridge but they don't provide examples so im not sure how it differs from normal induction (n=1, n=k, n=k+1).

Any help is appreciated.

Example below:
Screen Shot 2021-04-14 at 8.30.12 pm.png
 

tito981

Well-Known Member
Joined
Apr 28, 2020
Messages
326
Location
Orange
Gender
Male
HSC
2021
you just have to take 2 assumptions instead of 1. so it would be k, k+1 and then prove for k+2.
 

Drongoski

Well-Known Member
Joined
Feb 22, 2009
Messages
4,239
Gender
Male
HSC
N/A

Therefore true for n=1. Now Assume formula true for n <= k (stronger version), i.e.


Therefore if true for n=k, true also for n=k+1
Therefore true for all integers n >= 1.
 
Last edited:

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
Strong induction requires an assumption that is stronger than "Let k be a value of n for which the result is true."

In a recurrence relation like the one quoted above, , in order to use the relation in the second part of the proof, the preceding two values of (that is, and ) need to be known. You will thus need an assumption like

Let k be a value of n for where the result is true for both k = n and k = n - 1​

In order to make such an assumption, we must know that there is a case where the result is true for two consecutive terms, and so the first part must use prove the result for both the cases n = 1 and n = 2.

As @Drongoski has noted, an even stronger assumption that is sometimes used is

Let k be a value of n for where the result is true for all integers .​
 

mr.habibbi

Member
Joined
Oct 27, 2019
Messages
41
Gender
Male
HSC
2021
Strong induction requires an assumption that is stronger than "Let k be a value of n for which the result is true."

In a recurrence relation like the one quoted above, , in order to use the relation in the second part of the proof, the preceding two values of (that is, and ) need to be known. You will thus need an assumption like

Let k be a value of n for where the result is true for both k = n and k = n - 1​

In order to make such an assumption, we must know that there is a case where the result is true for two consecutive terms, and so the first part must use prove the result for both the cases n = 1 and n = 2.

As @Drongoski has noted, an even stronger assumption that is sometimes used is

Let k be a value of n for where the result is true for all integers .​
if the question had instead of , would we use n>=k instead of n=<k

also why do we need the '>' and '<' sign and not stick with n=k like in normal induction
 

cossine

Well-Known Member
Joined
Jul 24, 2020
Messages
583
Gender
Male
HSC
2017
if the question had instead of , would we use n>=k instead of n=<k

also why do we need the '>' and '<' sign and not stick with n=k like in normal induction
So you could just rewrite the expression
with Tn+2 as the subject.
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
So you could just rewrite the expression
with Tn+2 as the subject.
Yes, you could write it as



and let's assuming that it is true for all positive integers . It follows that:







etc.

It can now be seen (hopefully) that the result can be equivalently written as :



and thus matches the form of the original problem.
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
if the question had instead of , would we use n>=k instead of n=<k

also why do we need the '>' and '<' sign and not stick with n=k like in normal induction
I'm not following what greater than / less than signs that you mean?
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
can you spot any errors in m working?
I'm not keen on some of the setting out, but the working looks ok to me.

I see where you are using less than / less than or equal to signs and note that they would disappear if you stated the strong induction more formally, such as:

Theorem: If , , and for all integers show that for all positive integers .

Proof: By induction on

A In order to use the identity in part B, the general form must be shown to be true for the cases and .





So, we know that the result is true for the cases and .

B Now, let be a value of such that the result is true for both and . That is,



and


We must now prove that the result is true for . That is, we must prove that




So, if the result is true for both and , then it must also be true for .

C It follows from A and B by the process of mathematical induction that the result must be true for all positive integers .

----

If you use the stronger form of induction (making the assumption for all integers , the only change would be to the start of part B, which would become:

B Now, let be a value of such that the result is true for all . In particular, this means that:



and, so long as ,


etc

Note that this stronger assumption still requires that the result be established in part A for both and because invoking the recurrence relation requires knowledge of the truth of the general formula for the two preceding cases. Put another way, if you only proved the result for in part A then it would not be proved for at any point - part B works only if every case up to is true and then uses the recurrence relation to establish the result for ... but I can't say as there is no , and so part B cannot prove from . Part B proves the general formula for and every subsequent integer from knowing the formula is true for and , but those initial cases must be established separately, which is the purpose of part A, of course.

This is one reason that I prefer the weaker strong assumption in part B that I gave above - assume for and - because it is then obvious that my part A needs to establish two initial values. Making the stronger assumption of truth for may only require establishing a single initial value in part A, but it may (as in this case) require two initial values, and it is easy to not fully consider what is required in part A for a valid and complete proof.

---

Does this clarify what you are asking?
 

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

Top