(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}$ 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.
 A: 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*}$$
A: 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.
A: 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}.$$
A: 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}.$$
