Prove that expression is integer

Numerical experiments suggest that $\binom{2m}{m + k}\cdot\frac{3m - 1 - 2k^2}{2m - 1}$ is integer for all $-m \le k\le +m$. It means that expression evaluation could be implemented very efficiently, only using integer addition and multiplication.

However, I've failed to derive computationally efficient expression so far. The two ideas I have are linear combination of binomials, and recursion -- but more insight is needed to go further.

It equals $$\binom{2m}{m+k}\frac{3m-1-2k^2}{2m-1}=-(m-1)\binom{2m}{m+k}+4m\binom{2m-2}{m+k-1}.$$ I got it by expanding $3m-1-2k^2=2(m^2-k^2)-(2m^2-3m+1)=2(m-k)(m+k)-(2m-1)(m-1)$.

• Awesome! Thank you Fedor for your lightning-fast and razor-sharp response. Jul 12, 2015 at 15:37
• Wow... Stunning! Aug 31, 2016 at 8:59