MedVision ad

Induction. (2 Viewers)

kekeheaven

Member
Joined
Jun 20, 2006
Messages
69
Gender
Male
HSC
2007
Hi for the past 2 lessons. ive learnt The proof of induction. And to be honest with u im always the person that is left behind....because i cant understand what the teacher is saying... can anyone explain to me how induction works please? thankz.
 

SoulSearcher

Active Member
Joined
Oct 13, 2005
Messages
6,757
Location
Entangled in the fabric of space-time ...
Gender
Male
HSC
2007
Biki has a decent article on induction:
http://www.boredofstudies.org/wiki/index.php?title=Maths_Extension_1:Mathematics_Induction
So does wikipedia:
http://en.wikipedia.org/wiki/Mathematical_induction

Induction is simply proving that a general statement is true for all natural numbers, or a given boundary of natural numbers. It involves 2 steps:
1. Prove that the statement is true for the starting value of n = n0
2. Prove that whenever the statement is true for any positive integer k > n0, that it is true for k + 1
And thus, it is true for all positive integers n > n0

EXAMPLE: Prove via mathematical induction that 1+3+5+7+...+(2n-1) = n2
First Step:
When n = 1,
RHS = 12 = 1 = LHS
Therefore it is true for n = 1
Second Step:
Suppose that k is a positive integer for which the statement is true.
That is, suppose 1+3+5+7+...+(2k-1) = k2
We prove the statement for n = k+1
That is, we prove 1+3+5+7+...+(2(k+1)-1) = (k+1)2
LHS = 1+3+5+7+...+ (2k-1)+(2(k+1)-1)
= [1+3+5+7+...+ (2k-1)] + (2k+1), but using the induction hypothesis that 1+3+5+7+...+(2k-1) = k2,
= k2 + 2k + 1
= (k+1)2
= RHS
Third step, i.e. The Mantra
It is true for n = 1, and hence it must be true for n = 2 and so on. Hence it is true for all n.

In order to get better at induction, you are just going to have to do a lot a questions on induction.
 

who_loves_maths

I wanna be a nebula too!!
Joined
Jun 8, 2004
Messages
600
Location
somewhere amidst the nebulaic cloud of your heart
Gender
Male
HSC
2005
kekeheaven said:
Hi for the past 2 lessons. ive learnt The proof of induction. And to be honest with u im always the person that is left behind....because i cant understand what the teacher is saying... can anyone explain to me how induction works please? thankz.
The Principle of Mathematical Induction (both the weak and strong version, coupled with other techniques oftened called "backward induction") is a principle in mathematics used often to prove mathematical statements that generalise into an infinite class/family of numbers. It is a principle that is a direct consequence of mathematical logic and the Well-Ordering Axiom (which says that given any set of natural numbers, there is a least element to that set) of the Natural numbers, N.

Logically this is what the principle is saying:

1) Suppose that we know a formula/statement S(K) is true for some pronumeral, representing an integer, K.

2) Then IF we can go on to prove/show that the same statement holds (i.e. is true) for the pronumeral (K + 1), where K is the original assumed pronumeral and 1 is the specific integer "one", then it follows that we have shown that S(K+1) is true when S(K) is true.

3) Since K was arbitrarily (ergo, it was non-specific [this is why it's in bold] and so a pronumeral) then it means that IF S(kj) is true for some specific interger kj, then S(kj+1) must also be true where (kj + 1) is clearly also specific.

4) If we now let k = (kj+1), then by the same argument above S((kj+1) +1) = S(kj+2) must also be true.

5) Then by logical inductivism (a word used in the philosophy of science), it follows that the statement S(K) has the solution set:
K = {kj, kj+1, kj+2, kj+3, ...}

6) Conclusion: the statement 'S' is true for all integers greater than or equal to kj

7) Now, of course, we don't know what kj is initially. Since that would actually depend on the statement S. But IF we do know what it is (i.e. in the form of a specific integer) then we will know that S is true for all integers greater than kj as well IF we can prove that "S(K) true" ---> "S(K+1) true".


Usually you are given a statement S that is usually true for the first specific integer n = 1.
So if you go on to assume it's true for some n = K and show that S(K+1) must also be true, then you've essentially shown S is true for all integers >= 1.


Summary:

i) Begin all your inductive proofs by testing the given statement/formula with the smallest integer given in the conditions of the questions. Show that for that integer the statement is true. Then you have found a specific kj .

ii) Next, assume the truth of the statement for some n = K, where K is arbitrary.

iii) Show that, with the assumption in ii), S(K+1) is true. (this usually involves you showing that the given formula retains the same form except with (K+1) in the places where (K) used to be)

iv) Then by the Principle of Mathematical Induction, since we know already from i) that S is true for kj and proved in iii) that S is true for K+1 if it's true for K, then S must be true for:
{kj, kj+1, kj+2, ...}

Hope that helps.


P.S. It is not necessary nor fixed that the gap between each successive (and ordered) element of the solution set be = +1.
eg. if you are asked to prove a statement for, say, all even or odd numbers only then the gap would be +2 with the initial kj value an even or odd number respectively.


EDIT: Doing mathematics via exercises and examples is a great way of familiarising oneself with mathematical concepts and techniques. SoulSearcher's example above given in his post is something that should be read, learnt, and made sure is understood.
I always like textbooks that give examples as well as pure theory :p.

[Apologies SoulSearcher, I didn't see your post/example before I posted mine here.]
 
Last edited:

kekeheaven

Member
Joined
Jun 20, 2006
Messages
69
Gender
Male
HSC
2007
SoulSearcher said:
We prove the statement for n = k+1
That is, we prove 1+3+5+7+...+(2(k+1)-1) = (k+1)<SUP>2</SUP>
LHS = 1+3+5+7+...+ (2k-1)+(2(k+1)-1)
= [1+3+5+7+...+ (2k-1)] + (2k+1), but using the induction hypothesis that 1+3+5+7+...+(2k-1) = k<SUP>2</SUP>,
= k<SUP>2</SUP> + 2k + 1
= (k+1)<SUP>2</SUP>
.
i cant understand how this works
 

Riviet

.
Joined
Oct 11, 2005
Messages
5,593
Gender
Undisclosed
HSC
N/A
kekeheaven said:
i cant understand how this works
In mathematical induction, we assume that the given statement is true for n=k, where k is a random integer. We want to show that it is true for n=k+1 and hence deduce that it's true for n=(k+1)+1=k+2, n=(k+2)+1)=k+3... in other words the next integer and the next integer and the next integer and so on.
So when we prove the statement for n=k+1, we substitute n=k+1 into the given statement and work your way to making the LHS become the RHS, which proves that the statement is true for n=k+1 when LHS=RHS.
Now since we have assumed that the statement is true for n=k, we can sought of say that if this statement for k is true and we use this assumption in our proof for n=k+1 and successfully prove the statement being true for n=k+1, then we are able to conclude that since it is true for n=k and k=k+1, then it must be true for n=k+1+1=k+2, k+3, k+4, etc. Therefore, we are allowed to substitute our assumption for n=k into our n=k+1 proof.
Hope that helps.
 

kekeheaven

Member
Joined
Jun 20, 2006
Messages
69
Gender
Male
HSC
2007
Riviet said:
In mathematical induction, we assume that the given statement is true for n=k, where k is a random integer. We want to show that it is true for n=k+1 and hence deduce that it's true for n=(k+1)+1=k+2, n=(k+2)+1)=k+3... in other words the next integer and the next integer and the next integer and so on.
So when we prove the statement for n=k+1, we substitute n=k+1 into the given statement and work your way to making the LHS become the RHS, which proves that the statement is true for n=k+1 when LHS=RHS.
Now since we have assumed that the statement is true for n=k, we can sought of say that if this statement for k is true and we use this assumption in our proof for n=k+1 and successfully prove the statement being true for n=k+1, then we are able to conclude that since it is true for n=k and k=k+1, then it must be true for n=k+1+1=k+2, k+3, k+4, etc. Therefore, we are allowed to substitute our assumption for n=k into our n=k+1 proof.
Hope that helps.
Riviet thanks for putting time into writing it, but the way i can only understand this is by supporting it with an example, sorry if im asking too much i really am left behind..
 

SoulSearcher

Active Member
Joined
Oct 13, 2005
Messages
6,757
Location
Entangled in the fabric of space-time ...
Gender
Male
HSC
2007
Again, we go to my example.

Suppose that k is a positive integer for which the statement is true.
That is, suppose 1+3+5+7+...+(2k-1) = k2
Here in this step we have assumed that the given statement is true for n = k, as we have already shown in the first step that for n = 1, the statement is true.
We prove the statement for n = k+1
That is, we prove 1+3+5+7+...+(2(k+1)-1) = (k+1)2
Now in here, we are now trying to prove that for n=k+1, the statement is true. We substitute k+1 for n into the statement to help us see what we are trying to prove.
LHS = 1+3+5+7+...+ (2k-1)+(2(k+1)-1)
= [1+3+5+7+...+ (2k-1)] + (2k+1), but using the induction hypothesis that 1+3+5+7+...+(2k-1) = k2,
Now this is where some assumptions have to be made. We have already assumed that the statement is true for n=k, and notice that the series before the last term is equal to the assumption that we have made, so we subtitute that assumption into the induction process. If we are able to prove it for n=k and k=k+1, then we are able to say that it is true for n=k+1+1 = k+2, and so on.
= k2 + 2k + 1
= (k+1)2
= RHS
Once we have made that assumption, we then place it into the form we are trying to get it into.
If it is still confusing, then post again, and we will try to help again.
 

kekeheaven

Member
Joined
Jun 20, 2006
Messages
69
Gender
Male
HSC
2007
SoulSearcher said:
Again, we go to my example.

Here in this step we have assumed that the given statement is true for n = k, as we have already shown in the first step that for n = 1, the statement is true.
Now in here, we are now trying to prove that for n=k+1, the statement is true. We substitute k+1 for n into the statement to help us see what we are trying to prove.
Now this is where some assumptions have to be made. We have already assumed that the statement is true for n=k, and notice that the series before the last term is equal to the assumption that we have made, so we subtitute that assumption into the induction process. If we are able to prove it for n=k and k=k+1, then we are able to say that it is true for n=k+1+1 = k+2, and so on.
Once we have made that assumption, we then place it into the form we are trying to get it into.
If it is still confusing, then post again, and we will try to help again.
hmm i dont see how the LHS = RHS
 

Riviet

.
Joined
Oct 11, 2005
Messages
5,593
Gender
Undisclosed
HSC
N/A
Example: Prove by induction that 1+2+3+...+n = n(n+1)/2 for all positive integers, n.

If n=1,
LHS=1
RHS=1(1+1)/2
=2/2
=1
.'. the statement is true for n=1

Now we assume that the statement is true for n=k, where k is some random positive integer. In other words, we asssume that
1+2+3+...+k = k(k+1)/2

We want to show that the statement is true for n=k+1 because k+1 is the next integer after k. In the same way 3 is the integer right after 2 and 12 is the integer right after 11, but we use k+1 and k as a general case when proving the statement.

So we want to prove the statement is true for n=k+1, so we substitute n=k+1 into the original statement. For the left side of the statement, we originally had
1+2+3+...+n, which is the sum of all the integers from 1 to n. We want to find the sum of the integers from 1 to k+1 so we write
1+2+3+...+ k + (k+1), which is an expression for the sum of all the integers from 1 to k+1.
On the right side of the equation, we originally had n(n+1)/2, which was what the sum of the integers from 1 to n was equal to. But we want the RHS to be an expression for the sum of all the integers from 1 to k+1, so instead of using n, we substitute k+1:
(k+1)([k+1] + 1)/2 = (k+1)(k+2)/2

Putting it together, we are required to prove that for n=k+1:
1+2+3+...+ k + (k+1) = (k+1)(k+2)/2

So we start with LHS:

LHS=1+2+3+...+ k + (k+1)

We stop here momentarily, observing that the highlighted bit in red is identical to what we had assumed previously (above). Since we assumed that the statement is true for n=k, we can use this in our proof for n=k+1 by substituting the assumption:

LHS=1+2+3+...+ k + (k+1)

= k(k+1)/2 + (k+1) [by assumption]

We stop here again. Looking at our assumption (highlighted in blue and red above), and observing that the blue bit is equal to the red bit, so in the last line we simply replace the red bit with the blue bit which is allowed since we assumed them to be equal at the start.

LHS=1+2+3+...+ k + (k+1)

= k(k+1)/2 + (k+1) [by assumption]

= k(k+1)/2 + 2(k+1)/2

= [k(k+1) + 2(k+1)]/2, by adding the fractions with a common denominator

= [k2 + k + 2k + 2]/2

= [k2 + 3k + 2]/2

= (k+1)(k+2)/2 => notice we have arrived at what we wanted to prove (highlighted in green in this line and further up)

= RHS

.'. The statement is true for n=k+1.

At the start, we proved that the statement was true for n=1. We assumed it was true for n=k and successfully used this assumption to prove that it was true for n=k+1.

Remembering that k can be ANY positive integer, it could be 1, it could be 2, 3, etc. we can say that:
If the statement is true for n=k, then it is true for n=k+1 (we have just proved this).

Since the statement is true for n=1 (we proved this at the very start), then it must also be true for n=1+1=2 (because of the orange bit).

So we have just deduced that the statement must be true for n=2, so since it is true for n=2, then the statement is also true for n=2+1=3 (because of the orange bit).

So we have just deduced that the statement must be true for n=3, so since it is true for n=3, then the statement is also true for n=3+1=4 (because of the orange bit).

So we have just deduced that the statement must be true for n=4, so since it is true for n=4, then the statement is also true for n=4+1=5 (because of the orange bit).

As you can see, this will continue on and on and on until we get to:
......... so we have just deduced that the statement must be true for n=k-2, so since it is true for n=k-2, then the statement is also true for n=k-2+1=k-1 (because of the orange bit).

So we have just deduced that the statement must be true for n=k-1, so since it is true for n=k-1, then the statement is also true for n=k-1+1=k (because of the orange bit).

We must realise that this will continue on for n=k+2, k+3, k+4, k+5, etc. and since we started from n=1, we are able to deduce that the statement is true for all positive integers n from n=1 onwards, by the principal of mathematical induction.

I hope you understand mathematical induction better now. :)
 
Last edited:

SoulSearcher

Active Member
Joined
Oct 13, 2005
Messages
6,757
Location
Entangled in the fabric of space-time ...
Gender
Male
HSC
2007
Ok, we want to prove that 1+3+5+7+...+(2k-1)+(2(k+1)-1) = (k+1)2, in order to prove our induction case.
i.e. LHS = RHS, where LHS = 1+3+5+7+...+(2k-1)+(2(k+1)-1) and RHS = (k+1)2, when n=k+1
We have assumed that 1+3+5+7+...+(2k-1) = k2, when n=k
Now, using that assumption, we are going to try to prove that LHS = RHS, when n=k+1
Now LHS = 1+3+5+7+...+(2k-1)+(2(k+1)-1)
= [1+3+5+7+...+(2k-1)]+(2k+1)
Now notice the part inside the square brackets. That series is equal to k2, using our assumption that 1+3+5+7+...+(2k-1) = k2, when n=k. Therefore we substitute that into our equation.
= k2+2k+1
=(k+1)2
=RHS
Therefore it is proven that the statement is true for n=k+1.
Because we use the assumption that the statement is true for n=k, we are able to use that assumption when trying to prove that the statement is true for n=k+1.

EDIT: Damn Riviet is too fast for me. Better explanation as well :)
 

kekeheaven

Member
Joined
Jun 20, 2006
Messages
69
Gender
Male
HSC
2007
Riviet said:
Example: Prove by induction that 1+2+3+...+n = n(n+1)/2 for all positive integers, n.

If n=1,
LHS=1
RHS=1(1+1)/2
=2/2
=1
.'. the statement is true for n=1

Now we assume that the statement is true for n=k, where k is some random positive integer. In other words, we asssume that
1+2+3+...+k = k(k+1)/2

We want to show that the statement is true for n=k+1 because k+1 is the next integer after k. In the same way 3 is the integer right after 2 and 12 is the integer right after 11, but we use k+1 and k as a general case when proving the statement.

So we want to prove the statement is true for n=k+1, so we substitute n=k+1 into the original statement. For the left side of the statement, we originally had
1+2+3+...+n, which is the sum of all the integers from 1 to n. We want to find the sum of the integers from 1 to k+1 so we write
1+2+3+...+ k + (k+1), which is an expression for the sum of all the integers from 1 to k+1.
On the right side of the equation, we originally had n(n+1)/2, which was what the sum of the integers from 1 to n was equal to. But we want the RHS to be an expression for the sum of all the integers from 1 to k+1, so instead of using n, we substitute k+1:
(k+1)([k+1] + 1)/2 = (k+1)(k+2)/2

Putting it together, we are required to prove that for n=k+1:
1+2+3+...+ k + (k+1) = (k+1)(k+2)/2

So we start with LHS:

LHS=1+2+3+...+ k + (k+1)

We stop here momentarily, observing that the highlighted bit in red is identical to what we had assumed previously (above). Since we assumed that the statement is true for n=k, we can use this in our proof for n=k+1 by substituting the assumption:

LHS=1+2+3+...+ k + (k+1)

= k(k+1)/2 + (k+1)

We stop here again. Looking at our assumption (highlighted in blue and red above), and observing that the blue bit is equal to the red bit, so in the last line we simply replace the red bit with the blue bit which is allowed since we assumed them to be equal at the start.

LHS=1+2+3+...+ k + (k+1)

= k(k+1)/2 + (k+1)

= k(k+1)/2 + 2(k+1)/2

= [k(k+1) + 2(k+1)]/2, by adding the fractions with a common denominator

= [k2 + k + 2k + 2]/2

= [k2 + 3k + 2]/2

= (k+1)(k+2)/2 => notice we have arrived at what we wanted to prove (highlighted in green in this line and further up)

= RHS

.'. The statement is true for n=k+1.

At the start, we proved that the statement was true for n=1. We assumed it was true for n=k and successfully used this assumption to prove that it was true for n=k+1.

Remembering that k can be ANY positive integer, it could be 1, it could be 2, 3, etc. we can say that:
If the statement is true for n=k, then it is true for n=k+1 (we have just proved this).

Since the statement is true for n=1 (we proved this at the very start), then it must also be true for n=1+1=2 (because of the orange bit).

So we have just deduced that the statement must be true for n=2, so since it is true for n=2, then the statement is also true for n=2+1=3 (because of the orange bit).

So we have just deduced that the statement must be true for n=3, so since it is true for n=3, then the statement is also true for n=3+1=4 (because of the orange bit).

So we have just deduced that the statement must be true for n=4, so since it is true for n=4, then the statement is also true for n=4+1=5 (because of the orange bit).

As you can see, this will continue on and on and on until we get to:
......... so we have just deduced that the statement must be true for n=k-2, so since it is true for n=k-2, then the statement is also true for n=k-2+1=k-1 (because of the orange bit).

So we have just deduced that the statement must be true for n=k-1, so since it is true for n=k-1, then the statement is also true for n=k-1+1=k (because of the orange bit).

.'. We can now deduce that the statement is true for all positive integers, n, by the principal of mathematical induction.

I hope you understand mathematical induction better now. :)
Ill give u 2 thumbs up :)
 

kekeheaven

Member
Joined
Jun 20, 2006
Messages
69
Gender
Male
HSC
2007
SoulSearcher said:
EDIT: Damn Riviet is too fast for me. Better explanation as well :)
Dw soulsearcher, I get the point now and i also understand how ur example works ty for helping
 

Riviet

.
Joined
Oct 11, 2005
Messages
5,593
Gender
Undisclosed
HSC
N/A
I'm glad that you understand it now, the good thing about induction is it's basically the same structure everytime, with some slight variations you'll encounter as you get some practice with doing more questions. ;)
 

kekeheaven

Member
Joined
Jun 20, 2006
Messages
69
Gender
Male
HSC
2007
Riviet said:
I'm glad that you understand it now, the good thing about induction is it's basically the same structure everytime, with some slight variations you'll encounter as you get some practice with doing more questions. ;)
i agree since im really comfortable with doing all types of inductions, now... the 2nd level of indcution How is divisiblity done.
 

Trebla

Administrator
Administrator
Joined
Feb 16, 2005
Messages
8,385
Gender
Male
HSC
2006
The same principle applies in divisibility as with any other induction case where you prove a statement is true for one case and then prove it to be true for all numbers in a specified condition. You'll encounter 4 types of induction in Extension 1: (in ascending order of general difficulty)
- Equalities: these are the most common ones you'll encounter
- Divisibility: you prove a statement results in an integer that is divisible by another integer by manipulating the assumption, substituting a quotient for another variable and then factorising the required integer out
- Inequalities: you prove X > Y and bring in the logical thinking behind inequality reasoning and manipulation of the assumption for substitution
- Geometry: you prove a geometric result using certain known geometric properties (this is the hardest type but it has never been asked in HSC so far)
 

bos1234

Member
Joined
Oct 9, 2006
Messages
491
Gender
Male
HSC
2007
kekeheaven said:
Hi for the past 2 lessons. ive learnt The proof of induction. And to be honest with u im always the person that is left behind....because i cant understand what the teacher is saying... can anyone explain to me how induction works please? thankz.
yes this topic is very very confusing to UNDERSTAND.. my teacher said he only really understood it in 2nd year uni.. just remember the steps..

n=1. n=k n=K+1..

the 3rd step is the hardest,....
 

meowz0r

New Member
Joined
Sep 10, 2006
Messages
21
Location
Sydney
Gender
Male
HSC
2007
wow....great explanation... so great you made me dig through my email, look for my user/pass, find it was lost, reset it and log in. THANKS! :D
 

Grey Council

Legend
Joined
Oct 14, 2003
Messages
1,426
Gender
Male
HSC
2004
hrm, when i tutor, some guys have trouble understanding this topic.

without clouding the issue any further, ill just say that the MOST IMPORTANT thing is to sub in step 2 when doing step 3.

everything falls into place after that.

mm riviets posted up a superb explanation, learn from that, but if you are ever stuck in an exam, remember, subbing in the assumption from step 2 when doing step 3 is the key to doing induction problems.
 
Last edited:
Joined
Jan 16, 2006
Messages
195
Gender
Male
HSC
2007
Trebla said:
The same principle applies in divisibility as with any other induction case where you prove a statement is true for one case and then prove it to be true for all numbers in a specified condition. You'll encounter 4 types of induction in Extension 1: (in ascending order of general difficulty)
- Equalities: these are the most common ones you'll encounter
- Divisibility: you prove a statement results in an integer that is divisible by another integer by manipulating the assumption, substituting a quotient for another variable and then factorising the required integer out
- Inequalities: you prove X > Y and bring in the logical thinking behind inequality reasoning and manipulation of the assumption for substitution
- Geometry: you prove a geometric result using certain known geometric properties (this is the hardest type but it has never been asked in HSC so far)

hey yall,

you reckon its possible for anyone who's bothered to post up at least one example of each, esp inequalities, cuz im totally f*ckn confused with them.

thanks in advance guys.
 

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

Top