Mathematica Mathematical induction

  • Thread starter Benny
  • Start date
584
0
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:

Gokul43201

Staff Emeritus
Science Advisor
Gold Member
6,987
14
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.
 

matt grime

Science Advisor
Homework Helper
9,394
3
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
 
429
0
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

Staff Emeritus
Science Advisor
Gold Member
6,987
14
matt, you gave away the solution ! :grumpy:
 

matt grime

Science Advisor
Homework Helper
9,394
3
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.
 

Related Threads for: Mathematical induction

Replies
3
Views
2K
Replies
4
Views
2K
Replies
7
Views
3K
Replies
0
Views
1K
Replies
4
Views
2K
Replies
15
Views
4K
Replies
15
Views
3K
Replies
2
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top