Loading ...
Sorry, an error occurred while loading the content.

principle of mathematical induction

Expand Messages
  • Saim Rauf
    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
    Message 1 of 6 , Mar 29, 2011
    • 0 Attachment
      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
    • Tamim Shahriar
      Please check the files section of the group. 3/4 years ago I wrote a Bangla article on this topic. Regards, Subeen.
      Message 2 of 6 , Mar 29, 2011
      • 0 Attachment
        Please check the files section of the group. 3/4 years ago I wrote a Bangla article on this topic.


        Regards,
        Subeen.

        On Tue, Mar 29, 2011 at 4:28 PM, Saim Rauf <scorpion_hellfire95@...> wrote:
         

        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


      • Sulman
        tell me what problem u r face in dis topic i will try to explain it
        Message 3 of 6 , Mar 29, 2011
        • 0 Attachment
          tell me what problem u r face in dis topic
          i will try to explain it
        • Saim Rauf
          i need it fully explained cos i dont know even a little about it
          Message 4 of 6 , Mar 30, 2011
          • 0 Attachment
            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
            >
          • Tamim Shahriar
            Read this: http://f1.grp.yahoofs.com/v1/YBiUTcOlITfIuq1DwGFL7DvbDzwtrbLJzxc3WTGN2CMkCUjpRpGQfsDj3DA3RnNXevwYbb91gplcyUQz0ValFA/tutorials/tutorial_induction.pdf
            Message 5 of 6 , Mar 30, 2011
            • 0 Attachment
              Read this: http://f1.grp.yahoofs.com/v1/YBiUTcOlITfIuq1DwGFL7DvbDzwtrbLJzxc3WTGN2CMkCUjpRpGQfsDj3DA3RnNXevwYbb91gplcyUQz0ValFA/tutorials/tutorial_induction.pdf

              On Thu, Mar 31, 2011 at 12:35 PM, Saim Rauf <scorpion_hellfire95@...> wrote:
               

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



            • S. M. Mamun Ar Rashid
              Dear Saim:   Hope I am not much late in replying :)   Suppose, you have been asked to prove that 1 + 2 + 3 + ... ... ... + n = n(n+1)/2,where n is a positive
              Message 6 of 6 , Apr 16 10:39 AM
              • 0 Attachment

                Dear Saim:

                 

                Hope I am not much late in replying :)

                 

                Suppose, you have been asked to prove that

                1 + 2 + 3 + ... ... ... + n = n(n+1)/2, where 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]

                => 2S = 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)/2

                 

                If 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 n and found the statement to be true for every case. But it is not possible to test with all values of n since n has no limit.

                 

                (2) or, somehow, you have logically shown that IF the statement is true for a particular value of n, THEN it is automatically true for the next value of 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 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(k+1)/2 [we can only say this now]

                 

                (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. Now is it REALLY TRUE? Let's check: 

                LHS = k(k+1)/2 + (k+1) [using (i)] 

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

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

                 

                Since 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)/2

                So, 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
                >

              Your message has been successfully submitted and would be delivered to recipients shortly.