Combinatorial proof $\sum_i^{\lfloor{n/2}\rfloor} (-1)^i {n-i\choose i} 2^{n-2i} = n+1$

Solution 1:

With this problem the underlying poset consists of nodes $Q\subset [n-1]$ (the set of positions where a $01$ pair resides) which represent binary strings with $01$ appearing at those positions plus possibly some others. Note that the sets represented at some $Q$ are empty, namely when there is overlap between some two or more $01$ pairs, i.e. when there exists an $m$ such that $\{m,m+1\} \subseteq Q.$ The weights on the $Q$ are as usual $(-1)^{|Q|}.$ The cardinality of the set of strings represented at $Q$ is clearly $2^{n-2|Q|}.$ For a given cardinality $|Q|=q$ the number of nodes $Q$ with no overlap between the constituent pairs is obtained by placing some number of spaces (which will receive a binary digit), possibly empty, between the $q$ $01$ pairs whose length must add up to $n-2q:$

$$[z^{n-2q}] \frac{1}{(1-z)^{q+1}} = {n-2q+q\choose q} = {n-q\choose q}.$$

(There are two cardinalities here, the cardinality $|Q|=q$ of $Q$ and the cardinality $2^{n-2q}$ of the set of strings represented at $Q$.) Introducing $M$, the set of subsets of $[n-1]$ that do not contain a pair $\{m,m+1\}$ i.e. with no overlap and counting the strings represented at all $Q\in M$ multiplied by their weight yields the closed form

$$\sum_{Q\in M} (-1)^{|Q|} 2^{n-2|Q|} = \sum_{q=0}^{\lfloor n/2\rfloor} {n-q\choose q} (-1)^q 2^{n-2q}.$$

Here we have used the fact that the length $n$ of the string imposes the bound $n\ge 2|Q|.$

On the other hand, counting by computing the total weight contributed by each of the $2^n$ strings we find that a string that has no instance of the $01$ pair only appears at $Q=\emptyset$ with total weight $(-1)^{|\emptyset|} = 1.$ A string whose set of instances of the $01$ pair is exactly $P$ where $|P|\ge 1$ appears in all $Q\subseteq P$ for a total weight of zero since

$$\sum_{Q\subseteq P} (-1)^{|Q|} = \sum_{q=0}^{|P|} {|P|\choose q} (-1)^q = 0.$$

Observe that this works since $P\in M$ and $Q\subseteq P$ implies $Q \in M.$ We conclude from these weights that the above sum counts exactly those strings with no instance of the $01$ pair, these having weight one, and the others having weight zero. Therefore it is equal to

$$n+1.$$

As a remark, observe that the sum is not difficult to evaluate. We get

$$\sum_{q=0}^{\lfloor n/2\rfloor} {n-q\choose n-2q} (-1)^q 2^{n-2q} = 2^n [z^n] (1+z)^n \sum_{q=0}^{\lfloor n/2\rfloor} (-1)^q 2^{-2q} z^{2q} (1+z)^{-q}.$$

Here the coefficient extractor controls the range and we continue with

$$2^n [z^n] (1+z)^n \sum_{q\ge 0} (-1)^q 2^{-2q} z^{2q} (1+z)^{-q} \\ = 2^n [z^n] (1+z)^n \frac{1}{1+z^2/(1+z)/4} = 2^n [z^n] (1+z)^{n+1} \frac{1}{1+z+z^2/4} \\ = 2^n [z^n] (1+z)^{n+1} \frac{1}{(1+z/2)^2} = 2^n \sum_{k=0}^n {n+1\choose n-k} (k+1) (-1)^k 2^{-k} \\ = 2^n \sum_{k=0}^n {n+1\choose k+1} (k+1) (-1)^k 2^{-k} = (n+1) 2^n \sum_{k=0}^n {n\choose k} (-1)^k 2^{-k} \\ = (n+1) 2^n (1-1/2)^n = n+1.$$