5
$\begingroup$

Does anyone know something about the following sums? $$ S_m(n)=\sum\limits_{k=o}^n(-1)^k{mn\choose mk} $$ Notice that $S_m(n)=0$ for odd $n$, so we only consider $S_m(2n)$. It holds that $S_0(2n)=1$, $S_1(2n)=0$, $S_2(2n)=(-4)^n$, $S_3(2n)=\frac{2}{3}(-27)^n$, but $S_4(2n)$ is no longer a geometric progression.

$\endgroup$
4
  • $\begingroup$ $S_3(2n)=\dfrac23\cdot(-27)^n$ $\endgroup$
    – Lucian
    Sep 21 '14 at 12:00
  • $\begingroup$ $S_4(2n)=(-4)^n\bigg[18~T_n+(-1)^n\bigg]$, where $T_n$ takes the values $1,~32,~1089,~36992,~1256641$, $42688800,~1450162561,~49262838272,~1673486338689,~56849272677152$, etc. $\endgroup$
    – Lucian
    Sep 21 '14 at 12:32
  • $\begingroup$ $T_{n+1}\approx32~T_n$. Also, $S_5(2n)=(-25)^n~U_n$, where $U_n$ takes the values $1,~10,~246,~6100,~151270$, $3751250,~93024900,~2306866250,~57206531750,~1418628962500$, etc. $\endgroup$
    – Lucian
    Sep 21 '14 at 12:53
  • $\begingroup$ Notice that $U_{n+1}\approx25~U_n$. $\endgroup$
    – Lucian
    Sep 21 '14 at 13:05
3
$\begingroup$

For every sequence $(u(k))_k$, consider $$T_N(u)=\sum\limits_{k=0}^N{N\choose k}u(k),$$ and note that $S_m(2n)=T_{2mn}(u_m)$ where $u_m$ is defined by $u_m(k)=1$ if $2m$ divides $k$, $u_m(k)=-1$ if $m$ divides $k$ but $2m$ does not, and $u_m(k)=0$ for every other $k$. The sequence $(u_m(k))_k$ has period $2m$ hence there exists some coefficients $(c_j^m)$ such that, for every $k$, $$u_m(k)=\sum_{j=1}^{2m}c_j^m\zeta_m^{kj},$$ where $\zeta_m=\exp(\mathrm i\pi/m)$ is the primitive $2m$-th root of unity. This yields $$T_N(u_m)=\sum_{j=1}^{2m}c_j^m\sum\limits_{k=0}^N{N\choose k}\zeta_m^{kj}=\sum_{j=1}^{2m}c_j^m(1+\zeta_m^j)^N,$$ hence $$S_m(2n)=\sum_{j=1}^{2m}c_j^m(1+\zeta_m^j)^{2mn},\qquad\zeta_m=\exp(\mathrm i\pi/m).$$ One can note that the mean of $u_m$ is zero hence $c_{2m}^m=0$.

For example, if $m=4$, then $$4u(m)=\zeta_4^{k}+\zeta_4^{3k}+\zeta_4^{5k}+\zeta_4^{7k},\qquad\zeta_4=(1+\mathrm i)/\sqrt2,$$ hence all this leads (I think) to $$S_4(2n)=\frac{1+(-1)^nr^{4n}}2,$$ where $$r=\left|1+\zeta_4\right|^2=2+\sqrt2.$$

$\endgroup$
3
$\begingroup$

Start by restating the problem: we seek to evaluate $$S_m(n) = \sum_{k=0}^n (-1)^k {nm\choose km} = \sum_{k=0}^n (-1)^k {nm\choose nm-km}.$$

Introduce the integral representation $${nm\choose nm-km} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{nm}}{z^{nm-km+1}} \; dz.$$

This gives the following for the sum: $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{nm}}{z^{nm+1}} \sum_{k=0}^n \frac{(-1)^k}{z^{-km}} \; dz.$$

We may extend the sum to infinity because the integral correctly represents the binomial coefficient being zero for $k>n$ to get $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{nm}}{z^{nm+1}} \sum_{k\ge 0} \frac{(-1)^k}{z^{-km}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{nm}}{z^{nm+1}} \sum_{k\ge 0} (-1)^k z^{km} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{nm}}{z^{nm+1}} \frac{1}{1+z^m}\; dz.$$

Extracting coefficients we obtain $$[z^{nm}] (1+z)^{nm} \frac{1}{1+z^m} = \sum_{q=0}^{nm} {nm\choose nm-q} [z^q] \frac{1}{1+z^m} = \sum_{q=0}^{nm} {nm\choose q} [z^q] \frac{1}{1+z^m}.$$

Introduce $\rho_k = e^{i\pi/m + 2\pi ik/m}$ so that using partial fractions by residues on simple poles we have $$\frac{1}{1+z^m} = \sum_{k=0}^{m-1} \frac{\mathrm{Res}\left(\frac{1}{1+z^m}; z=\rho_k\right)}{z-\rho_k}.$$ This is $$\sum_{k=0}^{m-1} \frac{\frac{1}{m} \rho_k^{-(m-1)}}{z-\rho_k} = \sum_{k=0}^{m-1} \frac{\frac{1}{m} \rho_k^{-m}}{z/\rho_k-1}.$$

Substituting this into the sum formula yields $$\sum_{q=0}^{nm} {nm\choose q} [z^q] \sum_{k=0}^{m-1} \frac{\frac{1}{m} \rho_k^{-m}}{z/\rho_k-1} = - \sum_{q=0}^{nm} {nm\choose q} \sum_{k=0}^{m-1} \frac{1}{m} \rho_k^{-m} \rho_k^{-q}$$

Now $\rho_k^{-m} = -1$ so this yields $$\sum_{q=0}^{nm} {nm\choose q} \sum_{k=0}^{m-1} \frac{1}{m} \rho_k^{-q} = \frac{1}{m} \sum_{k=0}^{m-1} \sum_{q=0}^{nm} {nm\choose q} \rho_k^{-q} \\ = \frac{1}{m} \sum_{k=0}^{m-1} \left(1 + \frac{1}{\rho_k}\right)^{nm} = \frac{1}{m} \sum_{k=0}^{m-1} \left(1 + \rho_k\right)^{nm}.$$

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.