For some integer $z \ge 2$ and large integer $n$ and $ t=\lceil \log n\rceil $, what is an approximate value for the following partial binomial sum? $$ \sum_{i=0}^{n-t} \binom{n}{i}z^i .$$

Another related problem for the same parameters is approximating $$ \sum_{i=n/t}^n \binom{n}{i}z^i .$$


  • 1
    $\begingroup$ This is close to mathoverflow.net/questions/17202/… $\endgroup$ – Suvrit Nov 12 '15 at 5:32
  • 3
    $\begingroup$ In both cases the sum is asymptotic to $(1+z)^n$ with great precision, since you have given almost all of the binomial summation. $\endgroup$ – Brendan McKay Nov 12 '15 at 5:38
  • $\begingroup$ @BrendanMcKay true! I did not notice that $t$ is so small and took it to be arbitrary! $\endgroup$ – Suvrit Nov 12 '15 at 5:42
  • $\begingroup$ @BrendanMcKay Thanks. Do you any reference or hint for its proof? $\endgroup$ – Aryo Z Nov 12 '15 at 6:13
  • $\begingroup$ You can just be crude and say ${n \choose n-m} \leq n^m$ in this range. Thus the sum of the missing terms is at most $t n^t z^n$, which is exponentially smaller than $(1+z)^n$. $\endgroup$ – alpoge Nov 12 '15 at 7:18

Your Answer

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

Browse other questions tagged or ask your own question.