Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical induction

  1. Jul 29, 2005 #1
    I was told that the following can be proven by induction. Can someone explain to me how this can be done?

    I also have the following fact: If p|(ab) then either p|a, p|b or both.

    Let p be a prime number and let a_i, i = 1,2,3,...,n be integers. If p|(a_1)(a_2)...(a_n) then p divides at least one of the a_i.

    I'm not too sure how to state the the induction proposition/statement. Perhaps P_n is the statement that if p|(a_1)(a_2)...(a_n), p is prime and the a_i are integers then p divides at least one of the a_i. But what about the base case? I guess the base case just follows from the fact which I included earlier in this post. So how would I prove that p_k is true => p_(k+1) is true.

    The induction hyhpothesis would be if p|(a_1)(a_2)...(a_k) where p is prime and the a_i are integers, then p divides at least one of the a_i. Would I then write p_(k+1) is also true because:

    [tex]
    a_1 a_2 ...a_k a_{k + 1} = a_{k + 1} \left( {a_1 a_2 ...a_k } \right)
    [/tex]

    [tex]p|a_1 a_2 ...a_k[/tex] by hypothesis so that:

    [tex]
    p|a_{k + 1} \left( {a_1 a_2 ...a_k } \right)
    [/tex]

    Any help would be good.
     
    Last edited: Jul 29, 2005
  2. jcsd
  3. Jul 29, 2005 #2

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    1. You have not shown that if some prime divides [itex]\Pi_{i=1}^{k+1} a_i [/itex] then it also divides some a_i from that list. What you have shown is that if some prime divides [itex]\Pi_{i=1}^{k} a_i [/itex], then it also divides [itex]\Pi_{i=1}^{k+1} a_i [/itex]. This is not what is asked for.

    2. Note that it does not have to be the same prime that divides the product of the k+1 integers as that which divides the product of the k integers.
     
  4. Jul 30, 2005 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    if p divides a_1a_2..a_k then either p divides a_1 and we are done, or p divides a_2a_3..a_k and hence by induction divides one of the a_j for j is one of 2,..,k
     
  5. Jul 30, 2005 #4
    i think that using the second form of mathematical induction will work better.

    you assume that the statement is true for any integral statement less than the number of the statement you are trying to prove.

    and then you show that if all of those statements are true that it must follow that the statement in question is true.

    kinda difficult to get a hang of at first, but in my class we used it to prove the fundamental theorem of arithmetic and so forth.
     
  6. Jul 30, 2005 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    matt, you gave away the solution ! :grumpy:
     
  7. Jul 30, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    i don't think the solution is the important thing here since it is easy to write a solution invoking the magical 'by induction it follows that....', i think that the OP ought to look at what i wrote and realize that they don't understand how i magicked the 'by induction' from nowhere and that they ought to think about that. knowing the words for the answer and understanding the answer are different. of course if they simply wanted the solution for marks then more fool them.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Mathematical induction
  1. Mathematical induction (Replies: 24)

  2. Mathematical Induction (Replies: 3)

  3. Mathematical Induction (Replies: 15)

  4. Mathematical induction (Replies: 0)

Loading...