Induction. (1 Viewer)

[kekeheaven]

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]

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 = n₀
2. Prove that whenever the statement is true for any positive integer k > n₀, that it is true for k + 1
And thus, it is true for all positive integers n > n₀

EXAMPLE: Prove via mathematical induction that 1+3+5+7+...+(2n-1) = n²
First Step:
When n = 1,
RHS = 1² = 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) = k²
We prove the statement for n = k+1
That is, we prove 1+3+5+7+...+(2(k+1)-1) = (k+1)²
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²,
= k² + 2k + 1
= (k+1)²
= 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]

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

[Apologies SoulSearcher, I didn't see your post/example before I posted mine here.]</sub>

 

[kekeheaven]

Thanks for putting in time to help me , appreciate itz

 

[kekeheaven]

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]

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]

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]

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) = k²

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

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) = k²,

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.

= k² + 2k + 1
= (k+1)²
= 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]

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]

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

= [k² + k + 2k + 2]/2

= [k² + 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.

 

[SoulSearcher]

Ok, we want to prove that 1+3+5+7+...+(2k-1)+(2(k+1)-1) = (k+1)², 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)², when n=k+1
We have assumed that 1+3+5+7+...+(2k-1) = k², 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 k², using our assumption that 1+3+5+7+...+(2k-1) = k², when n=k. Therefore we substitute that into our equation.
= k²+2k+1
=(k+1)²
=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]

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

= [k² + k + 2k + 2]/2

= [k² + 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]

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]

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]

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]

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]

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]

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!

 

[Grey Council]

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.

 

[the-1-n-only-me]

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.