# A mod 2 binomial identity

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

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.

• Great! Also, after showing the recurrence relation, the base cases can also be handled by breaking into cases of $q$ even and $q$ odd and using strong induction. – JHF Nov 21 '18 at 15:54