Re: Sum of binomial coefficients.

Thanks again.
The only thing that still bother me is the following line you wrote:

C(n,k-1) < S(n,k) <= C(n,k-1)/(1-a).

Is the right-hand side inequality trivial? I don't see why it holds.

Thanks for you useful help,
Yochai.


Robert Israel wrote:
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

.

Relevant Pages

  • Re: Sum of binomial coefficients.
    ... The only thing that still bother me is the following line you wrote: ... Is the right-hand side inequality trivial? ... there are too many addents in the sum. ...
    (sci.math)
  • Re: probability equation
    ... On 28 Okt., 08:27, Robert Israel ... Assuming these are discrete random ... the sum being over all values b of that are possible for B when C=c. ...
    (sci.math)
  • Re: A Diophantine Equation
    ... consider the integer solutions of the equation ... If z has no prime factor 4k+1, then 2*z^2 is sum of two squares in just ... which are basically the same as those given by Robert Israel. ...
    (sci.math)
  • Re: sumif and array formulas
    ... First, if you can't bother to spell names correctly, don't bother ... including salutations. ... If you actually do want to sum CH:CW, ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Sum of binomial coefficients.
    ... To summaries this thread here is the final ... Robert Israel wrote: ... there are too many addents in the sum. ...
    (sci.math)