Induction proof problem (for set union)

[deviltaz]

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

Problem: Proof by induction that:

A₁ \cup A₂ \cup...\cupA_n=(A₁-A₂)\cup(A₂-A₃)\cup...\cup(A_n-1-A_n)\cup(A_n-A₁)\cup
(A₁\capA₂\cap...\capA_n)

 

[╔(σ_σ)╝]

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 :-).

 

[deviltaz]

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 ?

 

[deviltaz]

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:

A₁ \cup A₂ \cup...\cupA_n\cupA_n+1=(A₁-A₂)\cup(A₂-A₃)\cup...\cup(A_n-1-A_n)\cup(A_n-A_n+1)\cup(A_n+1-A₁)\cup(A₁\capA₂\cap...\capA_n\capA_n+1)

 

[╔(σ_σ)╝]

Try the suggestion I gave you. :-)