Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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:)?

share|cite|improve this question
Are you looking for asymptotic estimates? There is an exact formula... – Aryabhata Apr 5 '12 at 20:38
Yes, I would like have an asymptotic bound: – user28425 Apr 5 '12 at 20:47

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

share|cite|improve this answer
Why do you choose to write some letters like $\rm a$ this and not like $a$ this? – Pedro Tamaroff Apr 5 '12 at 21:04
@Peter: Some men just want to watch the world burn. – anon Apr 5 '12 at 21:09
Thank you very much! – user28425 Apr 5 '12 at 21:21

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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