Question:
if such $\forall i\in\{1,2,\cdots,\lfloor\dfrac{n-1}{2}\rfloor\}$,have $$2^{n-2i}|\sum_{k=i}^{\lfloor\frac{n-1}{2}\rfloor}\binom{k}{i}\binom{n}{2k+1}$$ Find all the positive intger $n$
I want to find this sum $\sum_{k=i}^{\lfloor\frac{n-1}{2}\rfloor}\binom{k}{i}\binom{n}{2k+1}$?this step is right?
this problem is post my frend xi yong wang
We have the sum
$$S_{n,q} = \sum_{k=q}^{\lfloor (n-1)/2\rfloor} {k\choose q} {n\choose 2k+1}.$$
Introducing
$${n\choose 2k+1} = {n\choose n-2k-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-2k}} (1+z)^n \; dz$$
this controls the range and we may extend $k$ to infinity, getting for the sum
$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n}} (1+z)^n \sum_{k\ge q} {k\choose q} z^{2k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-2q}} (1+z)^n \sum_{k\ge 0} {k+q\choose q} z^{2k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-2q}} (1+z)^n \frac{1}{(1-z^2)^{q+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-2q}} (1+z)^{n-q-1} \frac{1}{(1-z)^{q+1}} \; dz.$$
This is
$$\sum_{p=0}^{n-2q-1} {n-q-1\choose p} {n-2q-1-p+q\choose q} \\ = \sum_{p=0}^{n-2q-1} {n-q-1\choose n-q-p-1} {n-q-1-p\choose q}.$$
Observe that
$${n-q-1\choose n-q-p-1} {n-q-1-p\choose q} = \frac{(n-q-1)!}{p! q! (n-2q-1-p)!} \\ = {n-q-1\choose q} {n-2q-1\choose p}$$
so that the sum becomes
$${n-q-1\choose q} \sum_{p=0}^{n-2q-1} {n-2q-1\choose p} = 2^{n-2q-1} {n-q-1\choose q}.$$
where we have $q\le \lfloor (n-1)/2\rfloor.$ If this is to be a multiple of $2^{n-2q}$ then the binomial coefficient must be even. We apply Lucas' Theorem which says that a binomial coefficient ${n\choose p}$ is odd iff all the bits of $p$ are less than or equal to the corresponding bits of $n.$ Suppose first that $n$ is not a power of two and take $q = n - 2^{\lfloor \log_2 n\rfloor}.$ We have $q\ge 1$ as required. To verify the upper range start from $\lceil (n-1)/2\rceil \le n/2$ which follows by cases. This is $\lceil (n-1)/2\rceil \le 2^{-1 + \log_2 n}$ which is less than $2^{\lfloor \log_2 n\rfloor}$ so that $n-1 - \lfloor (n-1)/2\rfloor \lt 2^{\lfloor \log_2 n\rfloor}$ or $n - 2^{\lfloor \log_2 n\rfloor} \lt \lfloor (n-1)/2\rfloor + 1$ or $n - 2^{\lfloor \log_2 n\rfloor} \le \lfloor (n-1)/2\rfloor.$ This proves that the choice of $q$ is within the range. We thus have $n-q-1 = 2^{\lfloor \log_2 n\rfloor} - 1$, a string of one bits, which are larger than or equal to the bits of $q$ by inspection. Hence we have found an odd binomial coefficient and the claim does not hold when $n$ is not a power of two. The remaining case is for $n$ a power of two. We thus have $n-1$ a string of one bits. Hence the bits corresponding to $q$ in $n-1-q$ are the bits of $q$, but flipped. Now since all $q$ have at least one bit that is set we get a correspondong zero bit in $n-1-q.$ Hence the binomial coefficient is even. This works for all $q.$ Therefore the answer to the query is that $S_{n,q}$ is divisible by $2^{n-2q}$ with $q$ in the proposed range iff $n$ is a power of two.
Some of this material is sourced from the following MSE link.
