4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Hint: Use the principle of inclusion exclusion. Take all the sequences, subtract the sequences which have an instance of 01, add back in the sequences with two instance of 01, etc. When counting the $k$-way intersections, you will need to count the number of ways to select $k$ pairs of entries from a line of $n$. This can be thought of as the number of ways to tile a $1\times n$ rectangle with $k$ dominoes and $n-2k$ squares, which is answered by $\binom{n-k}k$. $\endgroup$ – Mike Earnest Apr 17 at 16:59
  • $\begingroup$ @MikeEarnest Thanks. You can submit your hint so I can accept it as best answer. $\endgroup$ – amir na Apr 17 at 17:09
  • 1
    $\begingroup$ ... and the tiled rectangle may be tiled in $[z^{n-2k}] \frac{1}{(1-z)^{k+1}} = {n-2k+k\choose k} = {n-k\choose k}$ ways. (Fill the $k+1$ spaces between the dominoes with a non-negative number of squares.) $\endgroup$ – Marko Riedel Apr 17 at 17:21
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ (+1) for this crystal-clear and elegant exposition. $\endgroup$ – Markus Scheuer Apr 19 at 7:06
  • $\begingroup$ Thank you. I hope it was useful. $\endgroup$ – Marko Riedel Apr 19 at 13:17
  • $\begingroup$ Yes, thank you. I think it is instructive and can be conveniently applied to similar problems this way. $\endgroup$ – Markus Scheuer Apr 19 at 15:07
  • $\begingroup$ Hi @Marko Riedel, can you help to proof a question similar to the one above, when I posted it I will let you know. I am a fan of your interesting work on combinatoric. $\endgroup$ – coffeee Apr 19 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.