(combinatorial and algebraic) proof that $\sum_{q=1}^n \binom{n}{q}\binom{n-q}{2k-2q}2^{2(k-q)} = \binom{2n}{2k} - \binom{n}{2k}2^{2k}$

Question

I arrived at the following identity throught an attempt at a homework problem: the LHS is my solution; the RHS, the book's one. And as far I have tested, they are equivalent. $$\sum_{q=1}^n \binom{n}{q}\binom{n-q}{2k-2q}2^{2(k-q)} = \binom{2n}{2k} - \binom{n}{2k}2^{2k}$$

The combinatorial meaning of this identity is rather intuitive as per the homework's verbatim:

"Find the number of ways of forming a group of $2k$ people from $n$ couples where $k,n \in \Bbb N$ and $2k \leq n$ so that at least one couple is included in such group".

That being said, the combinatorial meaning of the LHS (and even the RHS) is rather clear: it iterates over $q = \{1,2,...,n\}$ couples, selects $2k-2q$ couples from the remaining $n-q$ and then picks one person from each of these $2k-2q$ couples, which can be done in $2^{2k-2q}$ ways, to form the group. The RHS does this by composition: removing those groups that do not contain one couple.

However, while I know what the LHS is supposed to do, I don't know how it works. I know that the groups that do not contain 1 couple is given by $\binom{n}{2k}2^{2k}$ (after all, this is the case where $q=0$), but I have little idea as to how the $\binom{2n}{2k}$ term counts the "rest". And I have way fewer ideas about how would I prove this thing algebraically.

Later edit: I realized that the $\binom{2n}{2k}$ term simply counts the number of ways of grouping $2k$ people from the overall $2n$ people of the $n$ couples. So ofc all you'd need to do after that is remove those groups that do not contain 1 couple.

Answer 1

Algebraic proof. Your identity is equivalent to (note that the upper limit should be $k$ and the lower limit is $0$ because we moved $\binom{n}{2k}2^{2k}$ to the left hand side): $$\sum_{q=0}^k \binom{n}{q}\binom{n-q}{2k-2q}2^{2(k-q)} = \binom{2n}{2k}.$$ Now we have that $$\begin{align*} \sum_{q=0}^k \binom{n}{q}\binom{n-q}{2k-2q}2^{2(k-q)}&= \sum_{q=0}^k \binom{n}{q}2^{2(k-q)}[z^{2k-2q}] (1+z)^{n-q} \\ &=[z^{2k}]4^k(1+z)^n\sum_{q\geq 0} \binom{n}{q} \frac{z^{2q}}{4^q(1+z)^{q}} \\ &=[z^{2k}]4^k(1+z)^n\left(1+\frac{z^2}{4(1+z)}\right)^n\\ &=[z^{2k}]4^k\left(1+z+\frac{z^2}{4}\right)^n\\ &=[z^{2k}]4^k\left(1+\frac{z}{2}\right)^{2n}=\binom{2n}{2k}. \end{align*}$$

Answer 2

Here is a variation on the theme, a slightly different proof for enrichment. In seeking to evaluate

$$\sum_{q=0}^k {n\choose q} {n-q\choose 2k-2q} 2^{2k-2q}$$

we observe that (OP notes that $2k\le n$)

$${n\choose q} {n-q\choose 2k-2q} = \frac{n!}{q! \times (2k-2q)! \times (n+q-2k)!} = {n\choose 2k-2q} {n-2k+2q\choose q}.$$

This gives

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

Here the coefficient extractor enforces the upper limit of the sum and we find

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

Answer 3

Your equality is known in a somewhat different form. First, let me bring the $\binom{n}{2k}2^{2k}$ subtrahend from the right hand side onto the left, where it neatly fits into the sum as a $q=0$ addend. Thus, your equality becomes \begin{align} \sum_{q=0}^n \binom{n}{q}\binom{n-q}{2k-2q}2^{2(k-q)} = \binom{2n}{2k}. \end{align} Next, let me generalize this equality by replacing $2k$ by $k$, so it becomes \begin{align} \sum_{q=0}^n \binom{n}{q}\binom{n-q}{k-2q}2^{k-2q} = \binom{2n}{k}. \end{align} In this form, this is Exercise 2 in my Fall 2018 Math 5705 homework set #2, where I give two solutions.

Let me sketch the first solution here (see the above link for details and for the second, purely algebraic solution):

$\newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\tup}[1]{\left( #1 \right)}$ Imagine that you have $n$ pairs of shoes $\tup{L_1, R_1}, \tup{L_2, R_2}, \ldots, \tup{L_n, R_n}$, where the $2n$ shoes $L_1, R_1, L_2, R_2, \ldots, L_n, R_n$ are all distinguishable. How many ways are there to grab $k$ of these $2n$ shoes -- i.e., to pick a $k$-element subset of the set of all $2n$ shoes? On the one hand, there are clearly $\dbinom{2n}{k}$ many ways. On the other hand, here is a more complicated way to count these ways: Let's say you are grabbing $q$ complete pairs (i.e., there are $q$ many $i$'s such that you grab both $L_i$ and $R_i$). The number of ways to do so is $\dbinom{n}{q}\dbinom{n-q}{k-2q}2^{k-2q}$ (because there are $\dbinom{n}{q}$ many options for these $q$ complete pairs, then $\dbinom{n-q}{k-2q}$ many options to choose which of the remaining $n-q$ pairs you are grabbing one shoe from, and finally $2^{k-2q}$ options to choose between left and right shoes). Summing this over all possible values of $q$, we conclude that the total number of ways to grab $k$ out of the $2n$ shoes is $\displaystyle \sum_{q=0}^n \binom{n}{q}\binom{n-q}{k-2q}2^{k-2q}$. Now compare this with the first answer, and the identity follows.

I learned this exercise from Titu Andreescu, Zuming Feng, A path to combinatorics for undergraduates, Birkhäuser 2004, where the combinatorial 1st proof appears (as a particular case) as Example 2.11.

Answer 4

Here's a "snake oil" proof of the generalization noted by @darijgrinberg: \begin{align} \sum_{k \ge 0} \sum_{q=0}^n \binom{n}{q}\binom{n-q}{k-2q}2^{k-2q} z^k &= \sum_{q=0}^n \binom{n}{q} \sum_{k=2q}^{n+q} \binom{n-q}{k-2q}2^{k-2q} z^k \\ &= \sum_{q=0}^n \binom{n}{q} \sum_{k=0}^{n-q} \binom{n-q}{k}2^k z^{k+2q} \\ &= \sum_{q=0}^n \binom{n}{q} z^{2q} \sum_{k=0}^{n-q} \binom{n-q}{k}(2z)^k \\ &= \sum_{q=0}^n \binom{n}{q} z^{2q} (1+2z)^{n-q} \\ &= (1+2z)^n \sum_{q=0}^n \binom{n}{q} \left(\frac{z^2}{1+2z}\right)^q \\ &= (1+2z)^n \left(1+\frac{z^2}{1+2z}\right)^n \\ &= (1+2z)^n \left(\frac{(1+z)^2}{1+2z}\right)^n \\ &= (1+z)^{2n} \\ &= \sum_{k \ge 0}\binom{2n}{k} z^k \end{align} Hence $$\sum_{q=0}^n \binom{n}{q}\binom{n-q}{k-2q}2^{k-2q} = \binom{2n}{k}.$$