For and define together with the convention that if .

If then for every :

To be shown is that for each nonnegative integer . The base case is obvious.

Let it be that and that the statement is true for . Then:

showing that the statement is also true for .

By induction it has now been shown that for each nonnegative integer .

The sum will always be 2n , if i understand your question correctly

Expanding on the previous answers. I'm taking and to be constants which do not vary as . · If then the sum is within a constant of the last term. In fact the largest terms are approximately in geometric progression so you can get it quite accurately by computing the ratio. · If , almost all of the complete binomial expansion is present, so the sum equals . · If $α≈p$, then Russell's normal approximation will be good. (This needs some work to clarify whether the geometric approximation of the lower tail is good right up to the point where the normal approximation begins to be good. I think it is.)

First, what the Stirling bound or Stanica's result give is already a approximation of , hence the only problem can be with the sum. I don't know how to do that with such precision, but it's easy to compute it up to a constant factor by approximating with a geometric series: · · More generally, · · where . Cf. the appendix to my paper http://math.cas.cz/~jerabek/papers/wphp.pdf .

I'm going to give two families of bounds, one for when $k = N/2 + \alpha \sqrt{N}$ and one for when $k$ is fixed. · The sequence of binomial coefficients ${N \choose 0}, {N \choose 1}, \ldots, {N \choose N}$ is symmetric. So you have · $\sum_{i=0}^{(N-1)/2} {N \choose i} = {2^N \over 2} = 2^{N-1}$ · when $N$ is odd. · (When $N$ is even something similar is true · but you have to correct for whether you include the term ${N \choose N/2}$ or not. · Also, let $f(N,k) = \sum_{i=0}^k {N \choose i}$. Then you'll have, for real constant $\alpha$, · $ \lim_{N \to \infty} {f(N,\lfloor N/2+\alpha \sqrt{N} \rfloor) \over 2^N} = g(\alpha) $ · for some function $g$. This is essentially a rewriting of a special case of the central limit theorem. The Hamming weight of a word chosen uniformly at random is a sum of Bernoulli(1/2) random variables. · For fixed $k$ and $N \to \infty$, note that · $$ {{N \choose k} + {N \choose k-1} + {N \choose k-2}+\dots \over {N \choose k}} · = {1 + {k \over N-k+1} + {k(k-1) \over (N-k+1)(N-k+2)} + \cdots} $$ · and we can bound the right side from above by the geometric series · $$ {1 + {k \over N-k+1} + \left( {k \over N-k+1} \right)^2 + \cdots} $$ · which equals ${N-(k-1) \over N - (2k-1)}$. Therefore we have · $$ f(N,k) \le {N \choose k} {N-(k-1) \over N-(2k-1)}.$$

The sum of all binomial coefficients represents the total number of possible outcomes. For n coin flips, there are 2n possible sequences of heads and tails, which is what the corresponding binomial coefficients add up to.

Do you know that $(1+x)^n = \sum_{k=0}^{n} (^n_k)1^{n-k}x^{k} = (^n_0)+(^n_1)x+...+ (^n_n)x^n $? We need $x=1$ here.