0
votes
1answer
61 views

Is this possible or hopeless to try to prove?

If I have $x_1, ..., x_k=o(n)$ and $j=O(1)$. Is it possible to prove something like: $$\sum_{i=1}^k {n \choose j} \left(\frac{x_i}{n}\right)^j \left(1-\frac{x_i}{n}\right)^{k-j} \sim {n \choose j} ...
0
votes
0answers
21 views

Lower bound for a relative of the central binomial coeff

The central binomial coefficients $\binom{2m}{m}$ have g.f. $\frac{1}{\sqrt{1-4z}}$ and lower bound $\frac{4^m}{\sqrt{4m}} \le \binom{2m}{m}$. I'm interested in a related integer series $$T(2m, m) = ...
0
votes
0answers
27 views

relative error of Poisson approximation to sum of Binomial

We have given $X_i\sim Bin(n_i,p_i)$ for $i \in \{1,...,m\}$ and are interested in $$P[X \geq x]$$ for $X=\sum_{i} X_i$. As we can approximate $X_i$ by $Y_i \sim Poisson(n_i p_i)$, I wonder, ...
0
votes
0answers
49 views

Asymptotic complexity of $\sum_{k=1}^m \binom{2^m}{2^k} \binom{2^k}{2^{k-1}}$

I'm trying to examine the asymptotic complexity of $$f(m) = \sum_{k=1}^m \binom{2^m}{2^k} \binom{2^k}{2^{k-1}}$$ Question: How do you prove or disprove $f(m) \in \mathcal{O}(2^{2^m})$? Bonus ...
1
vote
1answer
98 views

Asymptotics of sum of Binomial Coefficients (Binomial distribution) - Poisson approximation?

Let $$f(n):=\sum_{i=k}^n {n \choose i } p^i (1-p)^{n-i}$$ where $k\geq 2$ is a fixed Parameter and $p=p(n) \in (0,1]$ depends on $n$ where $np\leq 1$. We consider $n \rightarrow \infty$. I've found ...
4
votes
3answers
117 views

Taking Limits with Binomial Coefficients

I am interested in taking the following limit: \begin{equation} \lim_{n \to \infty}\frac{{n/2 \choose m}}{n \choose m}. \end{equation} Provided that $m$ is fixed the solution is: \begin{equation} ...
2
votes
1answer
43 views

asymptotic estimate for this expression

How can I compute an asymptotic estimate for following expression? \begin{equation} A = ...
0
votes
0answers
29 views

asymptotic estimate for binomial coefficient

How can we compute the asymptotic estimate for binomial coefficient $Q = \binom{n}{s-t}$ with the $n,s \gg 1$ and $ t \ll n$ and $ t \ll s$
1
vote
3answers
62 views

A particular sum involving product of binomial coefficients

I am encountering a particular sum involving binomial coefficients, and I am looking for a possible closed-form solution. Here is the sum: suppose we are given two real numbers $a \in (0,1)$ and $b ...
4
votes
1answer
122 views

Recursive sequence with binomial coefficients

I have a sequence $\epsilon_i$ defined recursively for $i\ge 1$ as follows \begin{eqnarray*} \epsilon_1 &=& \frac{1}{p}\\ \epsilon_n &=& \frac{1}{1-(1-p)^n}\left( 1 + \sum_{j=1}^{n-1} ...
2
votes
2answers
162 views

Asymptotics of ${2^n \choose n}$?

How can one compute the asymptotics of ${2^n \choose n}$? I know it is bounded below and above by $\left(\frac{2^{n}}{n}\right)^n$ and $\left(\frac{2^{n}e}{n}\right)^n$. If I plug in Stirling's ...
9
votes
2answers
184 views

An extrasensory perception strategy :-)

Inspired by classical Joseph Banks Rhine experiments demonstrating an extrasensory perception (see, for instance, the beginning of the respective chapter of Jeffrey Mishlove book “The Roots of ...
6
votes
3answers
96 views

Show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$

In this question we are asked to show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$ What I did: $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \sum_{k=2012}^{n} 2^k*1^{n-k}\binom{n}{k} \leq ...
7
votes
3answers
270 views

How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $

Can we find $$ \sum_{k=0}^{n} \sqrt{\binom{n}{k}} \quad$$ This problem asked me my friend about a year ago, but I didn't know how to attack problem. Now, I am interesting in solution. Any suggestion? ...
1
vote
0answers
54 views

Find asymptotics in a given form $n=(e+o(1))^{f(s)}$

Let $p\to\infty$, $s={\binom {p^4} p}$ and $n={\binom {p^4}{p^2}}$. Find a function $f(s)$ in the following form $$\large n=(e+o(1))^{f(s)}$$ I've tried to use the followinf asymptotics for ...
3
votes
1answer
107 views

Find the constant $c$ in the equation $\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$

Find the constant $c$ in the equation $$\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$$ I've tried to use this asymptotics $$C_n^k \sim \frac{n^m}{m!} \sim e^{m\ln n ...
5
votes
1answer
121 views

Find asymptotic for $s(n)=\min\{m\in{\mathbb N}\mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$

I have some strange function: $s(n)=\min\{m\in {\mathbb N} \mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$ and I need to find asymptotics for it. I have a solution for this except one last step, I ...
0
votes
3answers
93 views

Asymptotic of binomial coeficient

I was doing a problem, and I found that I needed to calculate asymptotics for $$ \frac{1}{{n - k \choose k}}$$ Supposing $n = k^2$. Any help with this would be appreciated, thanks.
8
votes
3answers
120 views

Prove that $\prod_{k=1}^{\infty} \big\{(1+\frac1{k})^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$

This result, $$\prod_{k=1}^{\infty} \big\{\big(1+\frac1{k}\big)^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$$ is in a paper by Hirschhorn in the current issue of the Fibonacci Quarterly (vol. ...
0
votes
1answer
72 views

Summing ratio of partial sums of binomial coefficients

I would like to approximate the following when $n \gg k$. $\sum_{y = k + 1}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m} (y - 1)}{\sum_{m = 0}^k {y - 1 \choose m}}.$ The formula can be re-written ...
2
votes
0answers
88 views

Weighted sum of ratio of partial sum of binomial coefficients

I would like to approximate the following sum when $n \rightarrow \infty$ and $n \gg k$, $$\sum_{x = k}^n \sum_{y > x}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m}}{\sum_{m = 0}^k {y - 1 \choose ...
12
votes
2answers
341 views

Asymptotics of the sum of squares of binomial coefficients

We are trying to estimate the cardinality $K(n,p)$ of so-called Kuratowski monoid with $p$ positive and $n$ negative linearly ordered idempotent generators. In particular, we are interesting in the ...
2
votes
1answer
132 views

Proof of asymptotic expansion of binomial coefficient

here's the problem I'm currently stuck on: Prove that (for $k$ fixed): $$\binom{N}{k}=\frac{N^{k}}{k!}+O(N^{k-1})$$ I know that: $$\binom{N}{k}\le\frac{N^{k}}{k!}$$ But I'm not sure how to ...
3
votes
1answer
130 views

Is $\sum_{k=1}^{n} k^{k-1} (n-k)^{2n-k} \binom{n}{k} \sim\frac{n^{2n}}{2\pi} $?

How can you compute the asymptotics of $$T=\sum_{k=1}^{n} k^{k-1} (n-k)^{2n-k} \binom{n}{k}\;?$$ This is related to Asymptotics of sum of binomials . I attempted to simply use Stirling's ...
7
votes
1answer
275 views

How to compute the asymptotic growth of $\binom{n}{\log n}$?

I'm interested with tight bounds for: $$f(n)={n\choose{\log{n}}}$$ It sounds like it's something simple, but I can't get a nice expression I can use. Any ideas on how to do this?
14
votes
2answers
534 views

Asymptotics of sum of binomials

How can you compute the asymptotics of $$S=n + m - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+m-k}}{n^{n+m-1}}\;?$$ We have that $n \geq m$ and $n,m \geq 1$. A simple application of ...
1
vote
1answer
242 views

Sum of the first k binomial coefficients for fixed n

I am reading Remarks on a Ramsey theory for trees by Janos Pach, Jozsef Solymosi and Gabor Tardos. Let $k, d, n \geq 2$ be integers. Somethig interesting happens when $$2^{n/k} > \sum_{i=0}^{d-1} ...
0
votes
2answers
98 views

Sum with binomial coefficients and fraction

Is there a closed form known for $$ \phi(n,a,c)=\sum_{k=0}^n \binom{n}{k} a^k \frac{1}{k+c} $$ where $a <0$, $c>0$ and $n \in \mathbb{N}$? I know the answer for two special cases: $$ ...
11
votes
3answers
307 views

Closed form for $\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}$

Is it possible to write this in closed form: $$\sum_{k=0}^{n} k\binom{n}{k}\log\left(\vphantom{\Huge A}\binom{n}{k}\right)$$ Can you get something like $$n2^{n-1}\log(2^{n-1})$$
2
votes
1answer
99 views

Theta asymptotic for $\binom{2m}{m}$ [duplicate]

Show that $\binom{2m}{m} = \Theta\left(\frac{2^{2m}}{\sqrt{m}}\right)$ without using Stirling's approximation.
2
votes
2answers
124 views

Stirling's Approximation

A sharp Stirling's approximation form states that $$n! \sim \left(\frac{n}{e}\right)^n\sqrt{2\pi n}.$$ Use that form to show that: $$\binom{2m}{m} = \Theta\left(\frac{2^{2m}}{\sqrt{m}}\right).$$
1
vote
1answer
147 views

Inequality for binomial coefficients

Let $m \leq n, n \leq N$ and $0\leq k \leq m$. I am wondering what is the dependence of $n$ and $N$ that for all $m, k$ $$ \frac{{N-m \choose n-k}}{{N \choose n}}\leq 1. $$ Thank you for your help.
1
vote
1answer
217 views

Asymptotic for binomial coefficient with square root

I'm looking for asymptotic estimate for the binomial coefficient: $$ \ln{\binom{n}{[\sqrt{n}]}} $$ I assume Stirling's approximation can help, but I'm not sure I will get any good estimation with this ...
7
votes
1answer
285 views

Asymptotics for sum of binomial coefficients from Concrete Mathematics

Concrete Mathematics EXERCISE 9.25: Supposing \[ S_n = \sum_{k=0}^n \binom{3n}k \] Prove that \[ S_n = \binom{3n}{n}\left(2-\frac4n+O\left(\frac1{n^2}\right)\right) \] This sequence also ...
0
votes
1answer
99 views

Simple question about an asymptotic equality

Could someone please explain the second equality in Conjecture 1.1: http://arxiv.org/pdf/math/0501313v2.pdf ? (reproduced below) $(1+o(1))n^22^{1-n}=\left(\frac{1}{2}+o(1)\right)^n$ Initially, I ...
3
votes
2answers
402 views

Sum of cubes of binomial coefficients

I reduced a homework problem in combinatorics to giving an asymptotic estimate for $\sum_{k=0}^n{n \choose k}^3$. I assume Stirling's approximation can help, but I'm not experienced with making ...
4
votes
0answers
212 views

How fast does $\binom{n}{k}$ grow when $k \le n/2$?

How fast does $\binom{n}{k}$, $n$ fixed, grow when $k \le n/2$? Especially, I'm interested in the growth of the "inverse" of binomial coefficient $B_n(x) := \min \{k:\binom{n}{k} \ge x\}$. EDIT: ...
5
votes
1answer
1k views

Asymptotics for a partial sum of binomial coefficients

Good afternoon, I would like to ask, if anyone knows how to evaluate a sum $$\sum_{k=0}^{\lambda n}{n \choose k}$$ for fixed $\lambda < 1/2$ with absolute error $O(n^{-1})$, or better. In ...
7
votes
1answer
274 views

Bounds on $\sum_{k=0}^{m} \binom{n}{k}x^k$ and $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}, m<n$

I've read this interesting article by Woersch (1994) dealing with approximation of binomial coefficients (rows of Pascal's triangle). I'm just wondering if similar bounds exist for partial binomial ...
7
votes
2answers
321 views

Asymptotics of $\sum_{k=0}^{n} {\binom n k}^a$

I need to estimate the asymptotics of $$\sum_{k=0}^{n} {\binom n k}^a, \quad a>2, \quad a \in \mathbb{N}$$ In particular, I'm pretty much interested in $a=4$ case, but if the general solution ...
10
votes
2answers
1k views

Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?

I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$ $O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?
2
votes
2answers
1k views

How can I determine asymptotic growth of binomial coefficients?

Say I have a binomial coefficient $y=\binom{5n+3}{n+2}$ or $y=\binom{n^2+4}{3n}$ something of the sorts in terms of the variable $n$. How can I determine $f$ so that $y = O(f)$? Is there a general ...
7
votes
3answers
266 views

Asymptotic difference between a function and its binomial average

The origin of this question is the identity $$\sum_{k=0}^n \binom{n}{k} H_k = 2^n \left(H_n - \sum_{k=1}^n \frac{1}{k 2^k}\right),$$ where $H_n$ is the $n$th harmonic number. Dividing by $2^n$, we ...