Про индексы (и не только) в выражениях с суммами

[yovska]

Цитата:

Let $U$ be a universe of objects and let $P = \{p_1, p_2, p_3, \ldots, p_n\}$ be a set of properties that the objects may or may not have. For any $J \subseteq P,$ let $N_{\ge}(J)$ equal the number of objects in $U$ that have the properties in $J$ and possibly others, and $N_=(J)$ -- the number of objects in $U$ that have the properties in $J$ and no others. Show the number of objects in $U$ with none of the properties is $N_=(\emptyset) = \displaystyle{\sum_{J: J\subseteq P}(-1)^{|J|}N_{\ge}(J)}$.

Proof(?) with holes:

Suppose $|J| = 2$. Then some of the $N_=(J)$s are $N_=(\{p_1, p_7\}), \ N_=(\{p_{n-1}, p_n\})$ etc. There are $\binom n2$ such $N_=(J)$s. Generally, if $|J| = j$, then there are $\binom njN_=(J)$ objects all of whose properties are in $J$ meaning $\color{red}{\displaystyle{\sum_{|J| = j}(-1)^jN_=(J) = (-1)^j\binom njN_=(J)}}$. Summing both sides of the expression in $\color{red}{\text{red}}$ above, we have

$$\color{blue}{\sum_{j=0}^n\left(\sum_{|J| = j}(-1)^jN_=(J)\right) = \sum_{j=0}^n(-1)^j\binom njN_=(J)}$$

Since removing objects with $N_=(J)$ properties also removes objects with $N_{\ge}(J)$ properties(think of overlapping sets $A, B$ where $x \in A$ can also be in $A \cap B$), we can replace $N_=(J)$s in the expression $\color{blue}{\text{in blue}}$ above with $N_{\ge}(J)$s as follows:

$$\color{green}{\sum_{j=0}^n\left(\sum_{|J| = j}(-1)^jN_{\ge}(J)\right) = \sum_{j=0}^n(-1)^j\binom njN_{\ge}(J)}$$

Note that the number of objects in $U$ with none of the properties is $N_=(\emptyset)$ meaning the number of times $N_=(\emptyset)$ includes each object in $U$ is $1$ when the object has none of the properties and $0$ when the object has at least one property. If we can say the same thing about the expression $\color{green}{\text{in green}}$ above, then we can use it instead of $N_=(\emptyset)$.

Now assume an object in $U$ contains none of the properties in $P$. Then $|J| = 0$ meaning $\displaystyle{\sum_{j=0}^n\left(\sum_{|J| = 0}(-1)^0N_{\ge}(\emptyset)\right) = \color{purple}{\sum_{j=0}^nN_{\ge}(\emptyset) = N_{\ge}(\emptyset)}}$. [Here we want to be able to say "the expression $\color{green}{\text{in green}}$ above counts an object with no properties in $J$ only once". Exactly how, though?].

Suppose an object in $U$ contains $m$ properties in $P$ where $1 \le m \le n$. Then $|J| = m.$ Now $\displaystyle{\sum_{j=0}^n\left(\sum_{|J| = m}(-1)^mN_{\ge}(J)\right) = \sum_{j=0}^n\left((-1)^m\binom nmN_{\ge}(J)\right) = \color{brown}{N_{\ge}(J)\sum_{j=0}^n\left((-1)^m\binom nm\right) = N_{\ge}(J) \cdot 0} = 0}$. Thus the expression $\color{green}{\text{in green}}$ above doesn't even count an object with properties in $J$.

----------------------

У данного док-ва по меньшей мере три недостатка. Первый выделен фиолетовым цветом. С одной стороны кажется, что $\sum_{j=0}^nN_\ge(\emptyset)=(n+1)N_\ge(\emptyset)$, но с другой -- у выражения нет индексов. Другой вопрос задан непосредственно за фиолетовым выражением. Третьи недостаток выделен коричневым цветом. Здесь была попытка использовать $\displaystyle{\sum_{j=0}^n(-1)^j\binom nj = 0}$, но индексы в коричневой части не согласуются. Как это можно исправить?