I would like to show the following identity: for all $n, q \geq 0$,
$$\sum_k \binom{2k}{4k-2n} \binom{n+3q}{2k+2q+1} \equiv \binom{n+3q}{2q-1} \pmod{2}.$$
This has been computer-tested for all $n, q \leq 100$.
Remarks:
- My convention is that the binomial coefficient $\binom{m}{n}$ is nonzero only if $m \geq n \geq 0$.
- If it helps, in terms of generating functions, the sum on the left hand side is $$[x^n y^{2q-1}] \, \frac{(1+y)^{n+3q}}{x+x^2+y^2}.$$ Of course, the right hand side is equal to $[y^{2q-1}] \, (1+y)^{n+3q}$.
- The identity is not true without modulo $2$.
Best Answer
Here is a tentative proof:
We first notice that by Kummer theorem $\binom{2n}{2m} \equiv \binom{n}{m} \bmod 2$, so that it suffices to show that $$ S_q(n) \equiv T_q(n) \pmod 2$$ where \begin{align*} S_q(n):=&\sum_k \binom{k}{n-k}\binom{n+3q}{2k+2q+1}\\ T_q(n):=&\binom{n+3q}{2q-1}. \end{align*}
From here, the symbol $\sim$ means has the same parity as.
We have $\binom{a+1}{b+1}\sim \binom{a}{b+1}+\binom{a}{b}$ but also $\binom{a+2}{b+2}\sim \binom{a+2}{b}+\binom{a}{b}$.
We have \begin{align*} T_q(n+2)&\sim \binom{n+3q+2}{2q-1} \sim \binom{n+3q}{2q-1}+\binom{n+3q}{2q-3}\\ &\sim T_q(n) +\binom{n+3+3(q-1)}{2(q-1)-1} \\ &\sim T_q(n) +T_{q-1}(n+3) \\ T_q(n+3)&\sim T_{q+1}(n+2)+ T_{q+1}(n) \end{align*} On the other hand, we have \begin{align*}S_q(n+3)& \sim \sum_k \binom{k}{n+3-k}\binom{n+3q+3}{2k+2q+1}\\ &\sim \sum_k \binom{k}{n+2-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ &\sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ &+ \sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ &\sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3q+1}{2(k-1)+2q+3}\\ &+ \sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ &\sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)+1}\\ &+ \sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ & \sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3(q+1)}{2(k-1)+2(q+1)+1}\\ &+\sum_k\binom{k-1}{n+2-(k-1)}\binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)-1}\\ &+\sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\ &\sim S_{q+1}(n+2) +\sum_k\binom{k}{n+2-k}\binom{n+3(q+1)}{2k+2(q+1)-1}\\ &+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2) \\&+\sum_k\binom{k}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\\ &+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2)+\sum_k\binom{k-1}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\\ &+\sum_k\binom{k-1}{n-(k-1)}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\\ &+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2)+ S_{q+1}(n) \\&+\sum_k\binom{k-1}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2)+ S_{q+1}(n)+2\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2)+ S_{q+1}(n) \\&+\sum_k\binom{k-1}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ &\sim S_{q+1}(n+2)+ S_{q+1}(n)+2\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\ S_q(n+3)&\sim S_{q+1}(n+2)+ S_{q+1}(n) \end{align*}
So the parity of both $ S_q(n)$ and $ T_q(n)$ satisfy the same third order linear recurrence on $n$. Then in order to show that $ S_q(n) \sim T_q(n)$, it suffices to show that $ S_q(0) \sim T_q(0)$, $ S_q(1) \sim T_q(1)$ and $ S_q(2) \sim T_q(2)$.
$S_q(0)-T_q(0)$ is clearly an even integer since $$S_q(0)-T_q(0)= \binom{3q}{q+1}-\binom{3q}{q-1}=2 \binom{3q+1}{q-1}.$$
We have $T_q(1)-S_q(1)= \binom{3q+1}{q+2}-\binom{3q+1}{q-2}$. After some calculation we find $$T_q(1)-S_q(1)= 2\frac{5q+7}{3q+3}\binom{3q+3}{q-1}$$ which is an even integer since \begin{align*}\binom{3q+3}{q-1}(5q+7) &\equiv \binom{3q+3}{q-1}(2q+4)\pmod {3q+3}\\ &\equiv-\binom{3q+3}{q-1}(q-1)\pmod {3q+3}\\ &\equiv-\binom{3q+2}{q-2}(3q+3)\pmod {3q+3}\\ &\equiv 0\pmod {3q+3}\end{align*}
Also, after some calculation, it can be shown that \begin{align*} T_q(2)-S_q(2) &= \binom{3q+2}{q+3}-\binom{3q+2}{q-1}-\binom{3q+2}{q-3}\\ &= 2 \binom{3q+5}{q-1} \frac{54+301q+258q^2+59q^3}{(3q+5)(3q+4)(3q+3)}. \end{align*} Then, to complete the proof, we need to show that $$ \binom{3q+5}{q-1} (54+301q+258q^2+59q^3)\equiv 0 \pmod {(3q+5)(3q+4)(3q+3)}.$$ We have $$ (54+301q+258q^2+59q^3) \equiv (q-1)(66+47q+5q^2)\pmod {(3q+5)(3q+4)(3q+3)}.$$
Then $$ \binom{3q+5}{q-1} (54+301q+258q^2+59q^3) \equiv (3q+5)\binom{3q+4}{q-2}(66+47q+5q^2)\pmod {(3q+5)(3q+4)(3q+3)}.$$ Then it suffices to show that $$ \binom{3q+4}{q-2}(66+47q+5q^2)\equiv 0 \pmod {(3q+4)(3q+3)}.$$ But $3q+4$ and $3q+3$ are coprime, so we need to show that $$ \binom{3q+4}{q-2}(66+47q+5q^2)\equiv 0 \pmod {3q+4}$$ and $$ \binom{3q+4}{q-2}(66+47q+5q^2)\equiv 0 \pmod {3q+3}.$$ That is $$ \binom{3q+4}{q-2}(14-q^2)\equiv 0 \pmod {3q+4} \tag1$$ and $$ \binom{3q+4}{q-2}(24-q-q^2)\equiv 0 \pmod {3q+3}.\tag2$$
(1) is equivalent to \begin{align*} \frac{3q+4}{q-2}\binom{3q+3}{q-3}(14-q^2)&\equiv 0 \pmod {3q+4} \\ \binom{3q+3}{q-3}(14-q^2)&\equiv 0 \pmod {q-2}\\ 10\binom{3q+3}{q-3}&\equiv 0 \pmod {q-2}\\ 10\frac{q-2}{3q+4}\binom{3q+4}{q-2}&\equiv 0 \pmod {q-2}\\ 10\binom{3q+4}{q-2}&\equiv 0 \pmod {3q+4}.\\ \end{align*}
But the last line holds true indeed, because we know from here that \begin{align*} \binom{3q+4}{q-2}&\equiv 0 \pmod {\frac{3q+4}{\gcd(3q+4,q-2)}}\\ &\equiv 0 \pmod {\frac{3q+4}{\gcd(10,q-2)}}\end{align*}
There remains to show the validity of (2). We have
$$ \binom{3q+4}{q-2}(24-q-q^2)= (3q+3)\binom{3q+4}{q-4} \frac{3q+4}{(q-2)(q-3)}(24-q-q^2)$$ so that we need to show that $$ \binom{3q+2}{q-4}(3q+4)(24-q-q^2)\equiv 0\pmod {(q-2)(q-3)}. $$ That is
$$ \binom{3q+2}{q-4}(3q+4)(24-q-q^2)\equiv 0\pmod {q-2} $$ and $$ \binom{3q+2}{q-4}(3q+4)(24-q-q^2)\equiv 0\pmod {q-3}. $$ That is $$ 180\binom{3q+2}{q-4}\equiv 0\pmod {q-2} $$ and $$ 156 \binom{3q+2}{q-4}\equiv 0\pmod {q-3}. $$ That is $$ 180\frac{(q-2)(q-3)}{(3q+4)(q-2)}\binom{3q+4}{q-2}\equiv 0\pmod {q-2} $$ and $$ 156 \frac{q-3}{3q+3}\binom{3q+3}{q-3}\equiv 0\pmod {q-3}. $$
That is $$ 180(q-3)\binom{3q+4}{q-2}\equiv 0\pmod {(3q+4)(3q+3)} $$ and $$ 156\binom{3q+3}{q-3}\equiv 0\pmod {3q+3}. $$ That is $$ 180(q-3)\binom{3q+4}{q-2}\equiv 0\pmod {3q+4} \tag3$$ and $$ 180(q-3)\binom{3q+4}{q-2}\equiv 0\pmod {3q+3} \tag4$$ and $$ 156\binom{3q+3}{q-3}\equiv 0\pmod {3q+3}. \tag5$$
For (5) it holds true because we have $156=13\cdot 12$ a multiple of $12$ and from here, we have \begin{align*}\binom{3q+3}{q-3}&\equiv 0\pmod {\frac{3q+3}{\gcd(3q+3,q-3)}} \\ &\equiv 0\pmod {\frac{3q+3}{\gcd(12,q-3)}} \end{align*} For (3) it holds true because we have $180=18\cdot 10$ a multiple of $10$ and from here, we have \begin{align*}\binom{3q+4}{q-2}&\equiv 0\pmod {\frac{3q+4}{\gcd(3q+4,q-2)}} \\ &\equiv 0\pmod {\frac{3q+2}{\gcd(10,q-2)}} \end{align*}
We have seen that there exist an integer $K$, such that $\binom{3q+3}{q-3}=K\frac{3q+3}{\gcd(12,q-3)}$. Now, with the same argument from here, we have \begin{align*}\binom{3q+3}{q-2}&\equiv 0\pmod {\frac{3q+3}{\gcd(3q+3,q-2)}} \\ &\equiv 0\pmod {\frac{3q+3}{\gcd(9,q-2)}} \end{align*} so there exists an integer $L$ such that $\binom{3q+3}{q-2}=L\frac{3q+3}{\gcd(9,q-2)}$. Then \begin{align*} 180(q-3)\binom{3q+4}{q-2}&=180(q-3)\left(\binom{3q+3}{q-2}+\binom{3q+3}{q-3}\right)\\ &= (3q+3)\left( \frac{180L(q-3)}{\gcd(9,q-2)}+\frac{180K(q-3)}{\gcd(12,q-3)}\right). \end{align*} The second factor on the right hand side is clearly an integer and this establishes the validity of (4). The proof is finished here.