Mathematics, philosophy, code, travel and everything in between. More about me…

I write about

English | Czech
Choose your language. I write in English, but I translate many of my articles to Czech as well. Zvolte si jazyk. Píšu anglicky, ale řadu svých článků překládám i do češtiny.

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 theorem 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.

Inclusion-Exclusion Principle proof (messy) 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. 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! :-)

December 2, MMIX — Mathematics.