Mathematics, philosophy, programming, in-line skating and everything in between. More about me…

Inclusion-Exclusion Principle: Proof by Mathematical Induction For Dummies

Inclusion-Exclusion Principle is one of those double-faced theorems. Based on a transparent idea, but nearly incomprehensible when formulated and proved in mathematical terms. After seeing the proof demonstrated in a Discrete Mathematics course, the only comment I could think of was “What the hell?!”

Inclusion-Exclusion Principle.

I had spent a few hours over my notes from that lecture before I finally understood the proof from beginning to end. However, the moment of triumph was fleeting. Covered by several layers of comments, the notes started to resemble dadaistic poetry written in the Minoan Linear A script.

Blue ink: the original notes. Green ink: comments. Pencil: comments to comments. Crayons (three colors): labels.

So, I decided to rewrite the proof very carefully, very neatly, step by step, and with detailed commentary. Oh, and with COLORS! :-). The result is a text so simple that anybody must understand it. In fact, I expect to make a lot of money selling this highly instructive material to kindergartens and elite nurseries. Free download for a limited time only! :-)

Comments and constructive critique are welcome.

7 comments Add your own…

tal I April 27, MMX

This was great.
Thanks

Peter II August 27, MMXI

It's a crystal clear proof.  Thanks!

Vita III August 27, MMXI

Thank you, I am glad you liked it.

Joe IV May 16, MMXII

I just have one question. I understand the proof more-or-less, I know what it's trying to say, but i'm not a mathematician so I ask for better understanding.

What's the proof for that the summation won't loop forever?

I think Sum(J

Joe V May 16, MMXII

Ok... I lost the half of the comment.

So I think the Summation with the 'J subset of [n] and J not null' can choose exactly the same J subset forever (or there is a known rule for that when Summation and subsets are come to play? I'm not a mathematician, so just asking).

So I know the Theorem is true but it has some problems with it's exactness. Or not?

To be clear, for n = 2 the Sum can be A1+A1+A1+A1.... forever. Because {1} will be subset of [2] ( or {1,2}) and {1} won't be the empty set.

So the expected form won't be A1+A2-A1*A2.

By the way, very nice job, I like it, I just started to think about this problem.

Vita VI May 16, MMXII

Hi Joe, the notation

<$$ \sum_{J \subseteq [n], J \neq \emptyset} $$>

means “sum over all subsets of <$[n]$> except the empty set”. It does not mean that a subset can be used more than once. Just like you do not sum over a numeric index more than once when you use the common notation of

<$$ \sum_{i=1}^{n} \ldots $$>

neither do you use a set element more than once when you sum over a set:

<$$ \sum_{x \in X} \ldots $$>

Glad to be of any help,

~ Vita

Joe VII May 16, MMXII

Okay, thank you. I wasn't really sure about these bases. I get confused many times when summations and big operators come to play.

Speak your mind

Your name*

Your e-mail* (will not be displayed)

Your website (if you have one)

Please enter the current year (I hate spam)

Post Comment

Allowed HTML tags are a, blockquote, em, code, li, ol, p, pre, strong, ul. Links to other comments in the form “[IV]” or “[4]” are detected automatically.