Re: Sum of binomial coefficients.

In article <1161170057.508305.102860@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<twittoy@xxxxxxxxx> wrote:
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.

Please don't top-post.

As I said,

C(n,r-1) <= a C(n,r)

so C(n,r) <= a^(k-1-r) C(n,k-1)
and S(n,k) = sum_{r=0}^{k-1} C(n,r)
<= sum_{r=0}^{k-1} a^(k-1-r) C(n,k-1)
= (1 + a + a^2 + ... + a^(k-1)) C(n,k-1)
= (1-a^k) C(n,k-1)/(1-a)
<= C(n,k-1)/(1-a) since 0 < a < 1.

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

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? ... Robert Israel wrote: ... there are too many addents in the sum. ...
    (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: Calculate sum of product in Excel 2003
    ... to gmail if mailing direct) ... Sorry to bother you. ... I simply find the products then sum them. ...
    (microsoft.public.excel)
  • Re: UK number for complaint about Onetel?
    ... and inconvenience. ... if the sum is small they probably won't bother. ... Trouble with this way, although correct, you *may* end up having a 'bad ...
    (uk.telecom)
  • question about adding a scale in the second y-axis of a plot
    ... Is there any way to give a scale in the right-hand side y axis without really plotting anything? ... Sorry to bother u guys so much! ...
    (comp.soft-sys.matlab)