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

  • 0
    Are you looking for asymptotic estimates? There is an exact formula...2012-04-05
  • 0
    Yes, I would like have an asymptotic bound:2012-04-05

2 Answers 2