Mobius function of the power set I'm having difficulties understanding the derivation of the Mobius function for the power set, and would like to ask some questions.



*

*Does the equality "1" come about as the result of the induction hypothesis?

*How do we get "2" and the equality in green? I suspect that there are some identities there that I've forgotten.

 A: *

*The equality $$-\sum_{S\subseteq F\subset T}\mu_{S,F}=-\sum_{S\subseteq F\subset T}(-1)^{|F\setminus S|}$$ is where you use the induction hypothesis, that is, you want to show that $\mu_{S,T}=(-1)^{|T\setminus S|}$ holds for every $S\subseteq T$, but now you assume it holds true for any subset, $F$, in between $S\subseteq F\subset T$ (that is not equal to $T$).

*The equality $$-\sum_{S\subseteq F\subset T}(-1)^{|F\setminus S|}=-\sum_{i=0}^{t-1}\binom{t}{i}(-1)^i$$ is just a counting argument. Now let us look at the set $F\setminus S$, and let us assume that $|F\setminus S|=k$. How many sets are there with $k$ elements? When we pick our first element we have $t$ possibilities, for the next element $t-1$, and so on. In total we have $$t\cdot (t-1)\cdot\ldots\cdot (t-k+1)=\frac{t!}{(t-k)!}$$ possibilities. Now, we want to rearrange the elements and still have the same set, so we have to divide by $k!$, which is in how many ways we can arrange $k$ elements. This gives in total $$\frac{t!}{k!(t-k)!}=\binom{t}{k}$$ possibilities. Now you only have to check whether $\mu_{S,F}=\pm 1$, but this is easy, since by the induction hypothesis $\mu_{S,F}=(-1)^{|F\setminus S|}=(-1)^k$. This gives the desired sum.

*The green box is just the Binomial Theorem, which states that 

$$(x+y)^n=\sum_{i=0}^{n}\binom{n}{i}x^iy^{n-i}$$ 

With $x=-1, y=1$, this reduces to $$0=(-1+1)^n=\sum_{i=0}^{n}\binom{n}{i}(-1)^i$$
