Inclusion-exclusion conundrum: $\sum_{k=1}^{\lfloor n/2\rfloor} (-1)^{k-1}k\binom{n-k}{k}2^{n-2k} = \binom{n+1}{3}$

Question

I want a proof (preferably combinatorial) of the identity

$$ \sum_{k=1}^{\lfloor n/2\rfloor} (-1)^{k-1}k\binom{n-k}{k}2^{n-2k} = \binom{n+1}{3}. $$

I suspect that there is an inclusion-exclusion proof for a family of tilings of certain board with squares and dominoes. I believe so, because the summation index $k$ is at most $\lfloor \frac{n}{2}\rfloor $ and we know that the number of tilings of an $1\times n$ board with $k$ dominoes and $n-k$ squares is $\binom{n-k}{k}$. Perhaps we can look at squares colored in 2 possible colors.

However, I cannot see how can we define this family of tilings since each term in the summation depends on $k$ and the definition of each set should be, of course, independent of the summation index $k$. We might also use that $\binom{n+1}{3} = \binom{n}{3} + \binom{n}{2}$.

Answer 1

Identity 173 in Proofs That Really Count: The Art of Combinatorial Proof is similar: $$\sum_{k\ge 0} (-1)^k \binom{n-k}{k}2^{n-2k} = n+1.$$ The book gives two combinatorial proofs. The first one uses two-colorings of square-domino tilings (like you suggested), and the second one uses two-colorings of square tilings, as in Combinatorial proof $\sum_i^{\lfloor{n/2}\rfloor} (-1)^i {n-i\choose i} 2^{n-2i} = n+1$

---

Here's a snake-oil proof of your identity: \begin{align} &\quad \sum_{n \ge 0} \left(\sum_{k=1}^{\lfloor n/2 \rfloor} (-1)^{k-1} k\binom{n-k}{k}2^{n-2k} \right) z^n \\ &= \sum_{n \ge 0} \sum_{k\ge 0}(-1)^{k-1} k\binom{n-k}{k}2^{n-2k} z^n \\ &= \sum_{k\ge 0}(-1)^{k-1} k \sum_{n \ge 2k} \binom{n-k}{k}2^{n-2k} z^n \\ &= \sum_{k\ge 0}(-1)^{k-1} k \sum_{n \ge 0} \binom{n+k}{k}2^n z^{n+2k} \\ &= \sum_{k\ge 0}(-1)^{k-1} k z^{2k} \sum_{n \ge 0} \binom{n+k}{k} (2z)^n \\ &= \sum_{k\ge 0}(-1)^{k-1} k z^{2k} \frac{1}{(1-2z)^{k+1}} \\ &= -\frac{1}{1-2z}\sum_{k\ge 0} k\left(\frac{-z^2}{1-2z}\right)^k \\ &= -\frac{1}{1-2z}\cdot\frac{-z^2/(1-2z)}{(1+z^2/(1-2z))^2} \\ &= \frac{z^2}{(1-z)^4} \\ &= z^2 \sum_{n \ge 0} \binom{n+3}{3} z^n \\ &= \sum_{n \ge 0} \binom{n+1}{3} z^n \end{align}

Answer 2

I figured it out, using the solution of the Identity 173 mentioned by @RobPratt. Consider the set $\mathcal{T}$ of all tilings of an $n\times 1$ strip with dominoes and squares, such that we have at least one domino, one of the used dominoes is marked and in addition, each of the squares is colored either black or white. It is easy to see that we have exactly $k\binom{n-k}{k}2^{n-2k}$ such tilings which use $k$ dominoes.

Let $\mathcal{E}$ be the set of those tilings in $\mathcal{T}$, for which even number of dominoes are used, and let $\mathcal{O}$ be the set of those tilings in $\mathcal{T}$, for which odd number of dominoes are used. Note that the left-hand side of our identity is $|\mathcal{O}| - |\mathcal{E}|$. We will exclude exactly $\binom{n+1}{3}$ tilings in $\mathcal{O}$ and then we will show there is a simple involution mapping a tiling from one of the remaining tilings in $\mathcal{O}$ to a tiling in $\mathcal{E}$ and vice versa.

Consider the set of tilings $\mathcal{X}$ in $\mathcal{T}$ with exactly one domino (which has to be marked) and no white square followed by a black square (white-black pair). We will see that the number of these tilings is exactly $\binom{n+1}{3}$. Indeed, in an $n\times 1$ strip, we have $n+1$ spaces between consecutive squares in the strip, if we count the space before all of the $n$ squares and the space after them. Suppose that we choose $3$ of these spaces and let the second chosen space be the middle of the only domino in a tiling in $\mathcal{T}$. Let the other two selected spaces (on the left and on the right of the middle one) indicate that the coloring of the squares changes from black to white, if we look from left to right of the strip.

Now, let us define the following simple involution on $\mathcal{T'} = \mathcal{T}\setminus \mathcal{X}$. Every tiling in $\mathcal{T'}$ has either an unmarked domino or a white square followed by a black square. Given a tiling in $\mathcal{T'}$, go over it from left to right. If you see an unmarked domino first, replace the domino with a white-black pair. If you see a white-black pair first, replace it with a domino. The described map is obviously an involution on $\mathcal{T'}$, mapping a tiling in $\mathcal{E}$ to a tiling in $\mathcal{O}$, as the parity of the number of used dominoes always changes. Therefore, $|\mathcal{O}\setminus \mathcal{X}| - |\mathcal{E}| = 0$ and thus $|\mathcal{O}| - |\mathcal{E}| = |\mathcal{X}| = \binom{n+1}{3}$.