Computer experiments suggest that $$f_m(n,k)= \sum\limits_{j = 0}^n {{{( - 1)}^{n - j}}}\frac {2j + 1}{n + j + 1}\binom{2n}{n-j}\sum\limits_{l = 0}^{m - 1} \binom{mj+l+k}{2k}$$ satisfies $$f_m(k,k)=m^{2k+1}$$ and $$f_m(n,k)=0$$ for $n>k.$
Is there a simple proof of this fact?
I have a proof for both claims, but it’s fairly technical and I’ll elaborate later.
First, simplify the second sum into $\binom{m(j+1)+k}{2k+1}-\binom{mj+k}{2k+1}$. Then, regroup the terms per value of $a$ in $\binom{a}{2k+1}$, and use binomial magic to rewrite it as $$f_m(n,k)=\binom{m(n+1)+k}{2k+1}+\sum_{j=1}^n{\frac{j}{n+1}(-1)^{n-j-1}\binom{2n+2}{n-j+1}\binom{mj+k}{2k+1}}.$$
Let $$P=X\binom{X+k}{2k+1}=(2k+1)!^{-1}\prod_{i=0}^k{(X^2-i^2)}.$$
$P$ is an even polynomial with degree $2k+2$, dominant coefficient $(2k+1)!^{-1}$, and null constant term. Furthermore, $$mf_m(n,k)=\frac{1}{(n+1)}P((n+1)m)+\sum_{j=1}^n{\frac{P(jm)}{n+1}(-1)^{n-j+1}\binom{2n+2}{n-j+1}}.$$
Usual polynomial magic ensures that if $P$ has degree $0 \leq d \leq 2n+2$ and coefficient $\alpha$ before $X^{2n+2}$, then $$\sum_{j=0}^{2n+2}{P(j)(-1)^j\binom{2n+2}{j}}=(2n+2)!\alpha.$$
Therefore, $$S_t=\sum_{j=0}^{2n+2}{(-1)^j\binom{2n+2}{j}(n+1-j)^t}$$ is $0$ if $0 \leq t < 2n+2$ and $S_{2n+2}=(2n+2)!$ otherwise. As a consequence, if $0 < t \leq n+1$, $$S’_t=\sum_{j=1}^n{(-1)^{n-j+1}j^{2t}\binom{2n+2}{n-j+1}}=\sum_{j=1}^n{(-1)^j\binom{2n+2}{j}(n+1-j)^{2t}}=\frac{1}{2}\left(S_{2t}-2(n+1)^{2t}\right),$$ thus $S’_t=-(n+1)^{2t}$ if $0 < t \leq n$, and $S’_{n+1}=(2n+2)!/2-(n+1)^{2t}$.
In particular, with the above $P(X)=\prod_{i=0}^k{(X^2-i^2)}$, if $k < n$, then $\sum_{j=1}^n{\frac{P(jm)}{n+1}(-1)^{n-j+1}\binom{2n+2}{n-j+1}}=-\frac{P((n+1)m)}{n+1}$, QED.
When $k=n$, then $\sum_{j=1}^n{\frac{P(jm)}{n+1}(-1)^{n-j+1}\binom{2n+2}{n-j+1}}=-\frac{P((n+1)m)}{n+1}+\frac{1}{n+1}\frac{(2n+2)!m^{2n+2}}{(2k+1)!/2}$, QED again.