Induction proof problem (for set union) (1 Viewer)

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

I hope that someone can help me with the following problem:

Problem: Proof by induction that:

A1 [tex]\cup[/tex] A2 [tex]\cup[/tex]...[tex]\cup[/tex]An=(A1-A2)[tex]\cup[/tex](A2-A3)[tex]\cup[/tex]...[tex]\cup[/tex](An-1-An)[tex]\cup[/tex](An-A1)[tex]\cup[/tex]
(A1[tex]\cap[/tex]A2[tex]\cap[/tex]...[tex]\cap[/tex]An)
 
Last edited:
Can you attempt the problem first? Or at least show us your work thus far.

If you don't I am not sure you will get any help :-).
 
The problem is that I don’t have any idea how to use the ‘induction hypothesis’.
(I can use it If I add the set An+1 to the left side of the equation, but this leads me to nothing).
The hypothesis somehow should be used (I guess) to the right side of the equation (using set algebra properties, but I don’t know how…)
 
Have you heard of complete induction ?
 
Basically you want your base case to consist of A_1 and A_2. Prove equality for those cases and form your induction hypothesis by assuming the inequality is true for all m<n. Then show the inequality holds for n.

EDIT
Can you check your post for typos?

I see a term An-A1. Is that supposed to be there ?
 
Last edited:
Yes, its suppose to be there - that is the basic idea of the equation (of the sets union) - adding the ‘next set’ does not take into consideration the elements of the first one and the ‘previous’ does not take into consideration the elements of the actual set.

What I meant is that for the An+1 set, the equation would takes the following form:

A1 [tex]\cup[/tex] A2 [tex]\cup[/tex]...[tex]\cup[/tex]An[tex]\cup[/tex]An+1=(A1-A2)[tex]\cup[/tex](A2-A3)[tex]\cup[/tex]...[tex]\cup[/tex](An-1-An)[tex]\cup[/tex](An-An+1)[tex]\cup[/tex](An+1-A1)[tex]\cup[/tex](A1[tex]\cap[/tex]A2[tex]\cap[/tex]...[tex]\cap[/tex]An[tex]\cap[/tex]An+1)
 
Try the suggestion I gave you. :-)
 

The Physics Forums Way

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