- dear group members! Hope you ll be doing fine .i wanted to ask whether someone could explain principle of mathematical induction and principle of extended mathematical induc tion to me . Regards
Dear Saim:

Hope I am not much late in replying :)

Suppose, you have been asked to prove that

**1 + 2 + 3 + ... ... ... +**where*n*=*n*(*n+*1)/2,*n*is a positive integer.If you know the story associated with Karl Frederick Gauss, one of the greatest mathematicians of all time, then perhaps you would try this way

Let,

*S*= 1 + 2 + 3 + ... ... ... + (*n*-2) + (*n*-1) +*n*Then

*S*=*n*+ (*n*-1) + (*n*-2) + ... ... ... + 3 + 2 + 1 [just writing the terms in the descending order]Thus,

*S*+*S*= (*n*+1) + (*n*+1) + (*n*+1) + ... ... ... + (*n*+1) + (*n*+1) + (*n*+1) [There are*n*number (*n*+1) terms here]=> 2

*S*=*n**(*n*+1)=>

*S*=*n*(*n*+1)/2 [**Proved**]This is a very direct method, called

**Mathematical Deduction**. Here you started with the left hand side information, assumed it to be*S*for ease of work, and finally found that S =*n*(*n*+1). It was not even necessary for you to look into the right side at the beginning, because you knew that you would reach at the right had side after some time if everything goes smooth. This is a very**straightforward**method. Solving*x*= 2 from*x*^3 = 8 is another example of Mathematical Deduction.Now if the Deduction method does not strike your mind at first, you should not give up your efforts because you are an assiduous person, a quality very much essential to excelling in mathematics. You would have thought, well, let's check in an

**indirect way**:**1 + 2 + 3 + ... ... ... +***n*=*n*(*n+*1)/2If

*n*= 1, we have**1**at LHS. At RHS, we get 1(1+1)/2 = 1*2/2 =**1**. This is beautiful! We have proved that LHS = RHS when*n*= 1.But of course you would not leave it here. You would think what if

*n =*2*?*So, when

*n*= 2, LHS = 1 + 2 =**3**and RHS = 2(2+1)/2 = 2*3/2 =**3**. Again the statement is tested to be true for*n*= 2. You eagerly think what if*n =*3?When

*n*= 3, LHS = 1 + 2 + 3 =**6**and RHS = 3(3+1)/2 = 3*4/2 =**6**. The statement is tested to be true for*n*= 3 as well. At this point, you have grown confident enough to say that the statement should be true even for*n*= 4, 5, 6, ......., whatever. Ordinary people might claim on these three tests that the statement has been proved, but you are a mathematician! You cannot say that the statement is proved unless(1) either you have

**tested with all possible values of**and found the statement to be true for every case. But it is not possible to test with all values of*n**n*since*n*has no limit.(2) or, somehow, you have logically shown that IF the statement is true for a

of__particular value__*n*, THEN it is automatically true for theof__next value__*n*.For example, if you can show that IF the statement is true for

*n =*1, THEN it is also true for*n =*2; and if it is true for*n =*2, then it is also true for*n =*3; and if it is true for*n =*3, then it is also true for*n =*4; and so on*,*then you no longer need to test with all*n*'s.__You just need one test!__Now you may question did we not just prove this chain using our three tests for

*n =*1, 2, 3? NO! In our tests with*n =*1, 2, 3, the proofs were separate. We did not show that proof for*n =*1 automatically means proof for*n =*2.Now what should be the

**particular value of***n*? Should it be a fixed integer like 2, 4, 3457, etc.? In our three tests, we have seen that choosing a fixed number does not help because one proof does not result in the next proof. So, let's choose*n = k,*where*k*can be any integer, and we would show that IF the statement is true for*n*=*k,*it will be automatically true for*n = k+*1. And, let's proceed:(i) IF the statement is true for

*n*=*k*,**1 + 2 + 3 + ... ... ... +***k***=***k***(**[we can only say this now]*k+*1)/2(ii) Now we NEED TO SHOW that the statement is true for

*n = k+*1, i.e.**1 + 2 + 3 + ... ... ... +***k**+***(k+1)****=****(***k+*1)(*k+*1+1)/2.Let's check:__Now is it REALLY TRUE?__LHS =

*k***(***k+*1)/2 +**(**[using (i)]*k*+1)**= (**[taking (k+1) as common]*k*+1)(*k*/2+1)=

**(**RHS. We have really proved that that*k+*1)(*k+2*)/2 =.**IF the statement is true for***n*=*k,*it will be automatically true for*n = k+*1Since our

*k*can be any integer, so if we assume*n = k =*2, then we have proof for*n =*3. If we assume*n = k =*3, then we have proof for*n =*4. Now, again, that's not the end; mathematics is a very rigorous subject which should not have even the least uncertainty. Other mathematicians will argue that you have proved the statement for*n = k +*1 from*n = k.*But what about the values of*n*before*k?*You can say my*k (=n)*CAN BE 1, which means proof for*n =*2, which then means proof for*n*= 3, which then means proof for*n =*4*,*so on.But your mathematical friends are very recalcitrant. They would challenge that IF the statement is REALLY true for

*k =*1, ONLY then your chain of proofs will start. Ah, you instantly get the point. To shut their mouths, you only need to test that the statement is true for*n =*1.**1 + 2 + 3 + ... ... ... +***n*=*n*(*n+*1)/2So, when

*n*= 1, LHS = 1, RHS = 1. The statement is true for*n = k =*1. And the chain begins!This is called

**Mathematical Induction**, a very powerful method to test mathematical findings. I like this method very much because many times I imagine many peculiar results for my mathematical expressions. To test whether my whimsies are right, I just need to apply the Method of Induction, because if you apply the Method of Deduction in this case, you never know whether you are right or wrong, unless you really reach the conclusion; becausing failing to prove does not mean the conclusion is right or wrong, But you generally do not fail to prove or disprove using Induction. :)Regards,

S. M. Mamun Ar Rashid

**From:**Saim Rauf <scorpion_hellfire95@...>**To:**math_club@yahoogroups.com**Sent:**Thu, March 31, 2011 12:35:17 PM**Subject:**Re: [math_club] Re: principle of mathematical induction

i need it fully explained cos i dont know even a little about it

On Tue Mar 29th, 2011 2:22 PM EDT Sulman wrote:

>

>tell me what problem u r face in dis topic

>i will try to explain it

>