17
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
43
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Awesome! Thank you Fedor for your lightning-fast and razor-sharp response. $\endgroup$
    – Andrey Paramonov
    Commented Jul 12, 2015 at 15:37
  • $\begingroup$ Wow... Stunning! $\endgroup$
    – MR_BD
    Commented Aug 31, 2016 at 8:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .