6
$\begingroup$

I am sure there must be a known estimate for sums of the form: $$ S_d(n)=\sum_{j=0}^n \binom{dn}{dj} $$ where $d\ge 1$.

For $d=1$, the answer is obvious.

For $d=2$, the answer is here: Sum with binomial coefficients: $\sum_{k=0}^{n}{2n\choose 2k}$

UPDATE: I am interested in asymptotics. $$ d=3:\quad S_3(n)=\frac 13 8^{n}+(-1)^n \frac 23, $$

$$ d=4:\quad S_4(n)=\frac 14 16^{n}+(-1)^n 2^{2n-1} $$

$$ d=5:\quad S_5(n)=\frac 15 32^n+\frac 25\Biggl(-\frac {11}2+\frac{5\sqrt 5}{2}\Biggr)^n+ \frac 25\Biggl(-\frac {11}2-\frac{5\sqrt 5}{2}\Biggr)^n $$

The leading term is $\frac 1d 2^{dn}$, any bound for the remainder (with a reference:)?

$\endgroup$
  • $\begingroup$ Are you looking for asymptotic estimates? There is an exact formula... $\endgroup$ – Aryabhata Apr 5 '12 at 20:38
  • $\begingroup$ Yes, I would like have an asymptotic bound: $\endgroup$ – user28425 Apr 5 '12 at 20:47
9
$\begingroup$

Let $\omega$ be a primitive $d$ root of unity. Then define

$$\rm a:=\frac{1}{d}\sum_{j=0}^{d-1} \omega^{\,jk}=\begin{cases}1 & \rm k\equiv 0 ~\bmod d \\ 0 & \rm otherwise \end{cases}=\delta_k$$

To see the equality, first check the $\rm k\equiv0$ case, then the $\rm k\equiv 1$ case by symmetry ($\rm a=\omega \cdot a$), then notice the map $\rm j\mapsto \omega^{jk}$ sends the residues modulo $\rm d$ to the $\rm d/gcd(d,k)$th roots of unity, and it is specifically a $\rm \gcd(d,k)$-to-$1$ map, for any nonzero $\rm k$ (hence $\rm a=0$, going mod $\rm d/(d,k)$). (Also see the Kronecker delta function for a definition of the RHS.)

Using the binomial theorem again with interchange of summation, we have

$$\rm \begin{array}{c c}\frac{1}{d}\sum_{j=0}^{d-1} \big(1+\omega^j\big)^{nd} & \rm =\frac{1}{d}\sum_{j=0}^{d-1}\sum_{k=0}^{nd}\binom{nd}{k} \omega^{\,jk} \\ & \rm =\sum_{k=0}^{nd}\binom{nd}{k}\frac{1}{d}\sum_{j=0}^{d-1}\omega^{\,jk} \\ & \rm =\sum_{k=0}^{nd}\binom{nd}{k}\delta_k \\ & \rm =\sum_{\ell=0}^n \binom{nd}{n\ell}. \end{array}$$

Observe that the first leading term will be with $\omega=1$. Set $\rm \omega=e^{2\pi i/d}$; ordering $|1+\omega^j|$ by magnitude, we find the $(v+1)$th leading term is (for $v\le d/2$)

$$\begin{array}{c c} \rm \frac{(1+\omega^v)^{nd}+(1+\omega^{-v})^{nd}}{d} & = \rm \frac{(\omega^{v/2}+\omega^{-v/2})^{nd}(\omega^{vnd/2}+\omega^{-vnd/2})}{d} \\ & =\rm \frac{2}{d}\big(2\cos(2\pi v/d) \big)^{nd}\cos(\pi vnd)\end{array}$$


Similar considerations lead to an offset modular generalization:

$$\rm \frac{1}{d}\sum_{j=0}^{d-1}\omega^{-j\,r} \big(1+\omega^j\big)^{nd} =\sum_{\ell=0}^n \binom{nd}{n\ell+r}.$$

$\endgroup$
  • $\begingroup$ Why do you choose to write some letters like $\rm a$ this and not like $a$ this? $\endgroup$ – Pedro Tamaroff Apr 5 '12 at 21:04
  • 3
    $\begingroup$ @Peter: Some men just want to watch the world burn. $\endgroup$ – anon Apr 5 '12 at 21:09
2
$\begingroup$

It is well known that

$$\sum_{j=0}^{n} \binom{n}{dj} = \frac{1}{d} \sum_{j=0}^{d-1} (1 + w^j)^n$$

where $w$ is a primitive $d^{th}$ root of unity.

This you can get by considering

$$ (1+z)^n = \sum_{j=0}^{n} \binom{n}{j} z^j$$

Set $z = w^j$ for $j= 0$ to $d-1$ and add up.

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