Re: Sum of binomial coefficients.

In article <1160674393.754002.284210@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<twittoy@xxxxxxxxx> wrote:
Well... thank you.
But, my main interest here is in the case where n is not big compared
to k. For example when k=n/3. In this case, what can we say on
the sum?

The thing that is problematic for me is that if k is an order
of n, say

n/4, there are too many addents in the sum. And I wonder if still the
addends are small and thus: C(n,0)+C(n,1)+C(n,2)+...+C(n,k-1), is
approximately C(n,k). In approximately I mean up to constant
(multiplicative) factor. Or not?

C(n,r-1) = C(n,r) r/(n+1-r)

So if r <= k <= c n where c < 1/2,
C(n,r-1) <= C(n,r) k/(n+1-k) <= a C(n,r) where
0 < a = c/(1-c) < 1.
Then if S(n,k) = sum_{r=1}^{k-1} C(n,r), you have
C(n,k-1) < S(n,k) <= C(n,k-1)/(1-a).
Now if n -> infty and k -> infty with k/n -> c you have
C(n,k-1) /C(n,k) = k/(n+1-k) -> a
so in these circumstances you do get S(n,k) = Theta(C(n,k)),
i.e. bounds A C(n,k) < S(n,k) < B C(n,k) with 0 < A < B.

Robert Israel israel@xxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.

Quantcast