Proof of Mathematical Induction: Explained

[Benny]

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:

$$a_1 a_2 ...a_k a_{k + 1} = a_{k + 1} \left( {a_1 a_2 ...a_k } \right)$$

$$p|a_1 a_2 ...a_k$$ by hypothesis so that:

$$p|a_{k + 1} \left( {a_1 a_2 ...a_k } \right)$$

Any help would be good.

 

[Gokul43201]

1. You have not shown that if some prime divides $\Pi_{i=1}^{k+1} a_i$ then it also divides some a_i from that list. What you have shown is that if some prime divides $\Pi_{i=1}^{k} a_i$, then it also divides $\Pi_{i=1}^{k+1} a_i$. 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.

 

[matt grime]

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

 

[Brad Barker]

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.

 

[Gokul43201]

matt, you gave away the solution ! :grumpy:

 

[matt grime]

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.