# Prove that $\frac{m+n+2}{2(m+1)}{n\choose m}2^{(n-m)/2}$ is an integer

Let $m,n$ be positive integers, both odd or both even, with $n\ge m$. I think the following number $$\frac{m+n+2}{2(m+1)}{n\choose m}2^{(n-m)/2}$$ is always an integer, but I have trouble proving it.

-

Split $m+n+2$ as $m+1 + n+1$. You want $$\frac{1}{2} \binom{n}{m} 2^{(n-m)/2}$$ and $$\frac{n+1}{2(m+1)} \binom{n}{m} 2^{(n-m)/2}$$ to be integers. The first one is clear. For the second one, use $\displaystyle \binom{n+1}{m+1} = \frac{n+1}{m+1} \binom{n}{m}$.