Combinatorial proof $\sum_i^{\lfloor{n/2}\rfloor} (-1)^i {n-i\choose i} 2^{n-2i} = n+1$ Give a combinatorial proof (double counting) that $\sum_i^{\lfloor{n/2}\rfloor} (-1)^i {n-i\choose i} 2^{n-2i} = n+1$
There was a hint that maybe $n$ bit binary numbers without 01 may help. (eg. 1001, 10000110, 1010101 are invalid)
I can prove that count of $n$ bit binary numbers without 01 is n+1. Because they are one of these:
$00...00$
$10....00$
$110...00$
...
$11...11$
But I don't know how to prove LHS is equal to this. I think it maybe uses inclusion exclusion because the first term of sum is count of all $n$ bit binary numbers but I don't know what should I say for other terms.
 A: 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.$$
