2
votes
3answers
50 views

Set of solutions for a binomial inequality

I bumped into the following inequality: $${a-b\choose c}{a\choose c}^{-1} \le \exp\left(-\frac{bc}{a}\right)$$ Playing with it a little bit, trying to bound it asymptotically for large $a$'s, using ...
3
votes
1answer
40 views

Very loose bound on sum of first binomials

Let $n\geq k\geq 2$. Is it always true that $$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}\leq n^k?$$ The left-hand side is dominated by the term $\dfrac{n^k}{k!}$, so the statement should be true. ...
1
vote
1answer
33 views

Upper bound for ${n \choose cn}$

Is it true that for any $0<c<1/2$ and sufficiently large $n'$, there exists a $d <2$ such that ${n \choose cn} < d^n$ for all $n>n'$? Clearly we have to assume $cn$ is an integer. I ...
0
votes
1answer
41 views

Binomial coefficient - first two terms, proof of inequality

I've seen the following and I'm not sure whether it is true or not, and if yes, why it holds. $(1-p)^x \geq 1-p x$ for $p\in (0,1)$ and $x>0$. Do I need some additional Information to prove ...
1
vote
1answer
41 views

Lower bound functional binomial r.v.

I am trying to find a bound of the type $\mathbb{E}(|B-\frac{N}{2}|) \geq C \sqrt{N}$ Where $B$ is a binomial variable with parameters $(N,\frac{1}{2})$. The bound doesn't need to be very tight in ...
0
votes
1answer
44 views

Convexity of Binomial Term

I am reading a book on the probabilistic method, and the following claim was made: $\dbinom{y}{n}$ is convex. Why is this the case?
10
votes
3answers
287 views

Prove that $\,\,\displaystyle\inf_{n\in\mathbb N}\sum_{k=0}^{p}\lvert\sin{(n+k)^p}\rvert>0$

For any poistive integer number $p$, show that $$\inf\left\{ {\left\vert\sin{(n^p)}\right\vert+\left\vert\sin{(n+1)^p}\right\vert+\cdots+ \left\vert\,\sin{(n+p)^p}\right\vert\, :\,n\in ...
1
vote
0answers
45 views

Increasing fraction of sum of binomial coeffients

Let $n$ be a positive integer. Show that the quantity $$ \displaystyle \frac{ \displaystyle \sum_{i=1}^n { n+k \choose i-1 } }{ \displaystyle \sum_{i=1}^n { n+k+1 \choose i } } $$ is ...
2
votes
1answer
43 views

Proving Bernoulli's Inequality for $h<0$

I'm answering question 19 of chapter two of Spivak's Calculus and I can't seem to think of a way of doing it. I don't want to look up the answer so I thought I'd ask for a hint as to the general ...
8
votes
3answers
426 views

Which is greater, $300 !$ or $(300^{300})^\frac {1}{2}$?

Which is greater among $300 !$ and $(300^{300})^\frac{1}{2}$ ? The answer is $300 !$ (my textbook's answer). I do not know how to solve problems involving such large numbers.
2
votes
1answer
80 views

Is anyway to prove this: $\prod_{k=1}^{n}(a_{k})< (1/n^n)*(\sum_{k=1}^{n}(\sqrt{1+a_{k}*a_{k+1}}))^n$

$$ \prod\limits_{k=1}^{n}a_{k} < {1 \over n^{n}}\left(\,\sum_{k = 1}^{n}\,\sqrt{1+a_{k}\,a_{k+1}\,}\,\right)^n $$ ak and n are positive real number greater than 0. EDIT: a_{k+1} becomes a_{1} ...
1
vote
2answers
44 views

prove that for $n \ge 4, {{2n}\choose{n}} \ge n\cdot2^n$

Prove that for $n \ge 4$ $${{2n}\choose{n}} \ge n\times2^n$$ I tried like that: $T_4$: ${{8}\choose{4}} = 70 \ge 4\times2^4$ = 64 so it's ok $T_{n+1}$: $$\frac{(2n+2)!}{(n+1)!)(n+1)!} \ge ...
2
votes
0answers
42 views

Upper bound for tail of binomial expansion

Let $P,R,T$ be integer constants with $PR$ much greater than $T$. Suppose I flip a coin $PR$ times, each time (independent of other times) getting heads with probability $1/P$. The probability that I ...
0
votes
2answers
46 views

Prove an upper bound for the binomials

This is (supposed to be) an upper bound on the binomial coefficient: $$ \binom{n}{k} \le \frac{n^n}{k^k(n-k)^{n-k}}$$ If we prove it by induction for all integers $0 \le k \le n/2$, we can easily ...
1
vote
1answer
36 views

Direct proof that $\sum_{k=0}^m \binom{n}{k} \leq n^m$

Is there a short direct proof that $\sum_{k=0}^m \binom{n}{k} \leq n^m$ ? I can prove it by showing it is true for $m=2$ and then proving by induction. Is there a direct non-inductive proof?
6
votes
3answers
190 views

Short and intuitive proof that $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$

The simple inequality that $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$ has a number of different proofs. But is there a particularly intuitive, short and elegant proof that uses the natural ...
3
votes
1answer
92 views

Simplest proof that $\binom{n}{k} \leq \left(\frac{en}{k}\right)^k$

The inequality $\binom{n}{k} \leq \left(\frac{en}{k}\right)^k$ is very useful in the analysis of algorithms. There are a number of proofs online but is there a particularly elegant and/or simple proof ...
0
votes
1answer
59 views

Inequality with a sum and factorial

For a homework assignment we have the following question that I'm stuck on. Let $ 0 \leq y \leq 1 $ be given. $\forall m \in \mathbb{N}$, define $ \displaystyle S_m(y)=\sum_{k=0}^m \binom{m}{k}y^k$. ...
4
votes
1answer
224 views

Proving $\binom{2n}{n}\ge\frac{2^{2n-1}}{\sqrt{n}}$

Prove that $$\binom{2n}{n}\ge\dfrac{2^{2n-1}}{\sqrt{n}}$$ By the way: I have see $$\binom{2n}{n}\ge\dfrac{4^n}{2n}=\dfrac{2^{2n-1}}{n}$$ proof: Applying the binomial theorem ...
12
votes
7answers
476 views

Prove that $2^n < \binom{2n}{n} < 2^{2n}$

Prove that $2^n < \binom{2n}{n} < 2^{2n}$. This is proven easily enough by splitting it up into two parts and then proving each part by induction. First part: $2^n < \binom{2n}{n}$. The ...
3
votes
1answer
221 views

Average absolute value of sum with Rademacher random variables

Let $a_1, \ldots, a_n $ be independent Rademacher random variables with distribution $P(a_i=1) = P(a_i=-1) = \frac 12$. Estimate from below $$E \left|\sum_{i=1}^n a_i\right|.$$ I've reduced this ...
5
votes
2answers
230 views

Proof of inequality $\sum\limits_{k=0}^{n}\binom n k\frac{5^k}{5^k+1}\ge\frac{2^n\cdot 5^n}{3^n+5^n}$

Show that $$\sum_{k=0}^{n}\binom n k\frac{5^k}{5^k+1}\ge\frac{2^n\cdot 5^n}{3^n+5^n}$$ where $$\binom n k=\frac{n!}{k!(n-k)!}$$
6
votes
1answer
221 views

Lower bound on binomial coefficient

I encountered the following claim $$\frac{1}{n+1}2^{nH_2(k/n)} \le \binom{n}{k} \le 2^{nH_2(k/n)}$$ where $H_2$ is the binary entropy function. The upper bound is rather well known but how does one ...
1
vote
0answers
198 views

proving inequality for combinatorial sum

If somone can prove the following for every $d\leq r$ (for $d=0,1$ its easy, see below, the case d=r may be also simple, I didn't find something helpful) $$\frac{(d!)^2}{2^{n-2d}}\sum_{k=0}^{n}{n ...
5
votes
4answers
193 views

Proving $\binom{2n}{n}\le 4^n$ for all $n$ by smallest counterexample

Prove $$\binom{2n}{n}\le 4^n$$ for all natural numbers $n$ by smallest (minimal) counterexample. My attempt: First, $$\binom{2n}n = \frac{(2n)!}{(n!)^2} \le 4^n\;.$$ We know that $x\ne 0$ because ...
16
votes
4answers
526 views

Proving that $\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\frac{1}{2}n^n$

How can we prove that $$\displaystyle\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\dfrac{1}{2}n^n$$ where $\displaystyle\binom{n}{i}=\dfrac{n!}{i!(n-i)!}$. This inequality is very interesting. I ...
1
vote
0answers
175 views

how to solve the following expectation? closed-form expression or approximation

Suppose there is a binomial random variable $X\sim B(n-1,p)$,how to solve the following expectation $$E[(1- b^{X})^{m}]$$ where $b\in (0,1]$ and $m\in \mathbb{N} $ are all constants.I have tried my ...
2
votes
0answers
108 views

Inequality with binomial coefficient

Let $n$ be a natural number, $m\in [-n, n]$. Let $p=0,\ldots, \frac{n+m}{2}$. Show, that for all $p$, $$ {n \choose \left[{\frac{n+m}{2}}\right]}\geq \frac{2^{n+1/2}}{\sqrt{n-p/2}}. $$ Thank you for ...
1
vote
1answer
139 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.
0
votes
2answers
80 views

Inequality with binomial coefficients

Let $n, l \in \mathbb{N}, l\leq n$ be fixed. Let $k\in \mathbb{N}$ with $0 \leq k \leq l$. How to show the following? $$ {2n-l\choose n-k}\leq {2n-l \choose \frac{2n-l}{2}} $$
2
votes
1answer
83 views

Wellner Inequality

Working on an exercise from Shorack's Probability for Statisticians, Ex 4.6 (Wellner): Suppose $T \simeq$ Binomial$(n,p)$. Then use the inequality $$\mu(|X| \ge \lambda) \le ...
1
vote
0answers
107 views

Binomial coefficient intervals (inequality)

For given $N$, $x$ and $k$ such that $0\leq x<N$ and $2\leq k\leq \left\lfloor \frac{N+1-2x}{2}\right\rfloor $, does it exist $p,$ $2\leq p\leq \left\lfloor \frac{N+1}{2}\right\rfloor $ such that ...
4
votes
1answer
212 views

Inequality involving sums of fractions of products of binomial coefficients

Let $n\in\mathbb{N}$. For $0\le l\le n$ consider \begin{equation} b_l:=4^{-l} \sum_{j=0}^l \frac{\binom{2 l}{2 j} \binom{n}{j}^2}{\binom{2 n}{2 j}}\text{.} \end{equation} Do you know a technique how ...
2
votes
3answers
352 views

Two inequalities with binomial coefficients

I have two inequalities that I can't prove: $\displaystyle{n\choose i+k}\le {n\choose i}{n-i\choose k}$ $\displaystyle{n\choose k} \le \frac{n^n}{k^k(n-k)^{n-k}}$ What is the best way to prove ...
3
votes
2answers
237 views

Lower Bound of Central Binomial Coefficients

I would like to prove by induction the following inequality: $\frac{4^n}{n+1} < \binom{2n}{n}$, for all natural numbers n > 1. Any hints?
1
vote
3answers
154 views

Combinatorial inequality $\binom{n}{j}\leqslant 2^n$

I was trying to prove (or to find a counterexample) of the following inequality: $$\binom{n}{j}\leqslant 2^n$$ As I coudn't find a proof/counterexample, I tested some numbers and could see it ...
2
votes
1answer
117 views

Comparing two binomial coefficient sums

Let $j \in N, n\in N, n>1, q\geq 2$. I would like to show that $$ \sum_{j=\frac{n}{\ln n}}^{\sqrt n/2}(2j-n)^q{n \choose j}<\sum_{j=\sqrt n/2}^{{\frac n2}}(2j-n)^q{n \choose j} $$ Any help would ...
-1
votes
3answers
277 views

Prove a binomial inequality

I would like to prove the following inequality: $$ {m+n \choose m} \ge \frac{(n+1)^m}{m!} $$ Any hints?
4
votes
1answer
273 views

An inequality involving binomial coefficients

For $k\leq n$, how do I prove that ${2n \choose n}(1-\frac{k}{n})^{k}\leq{2n \choose n+k}$?
8
votes
1answer
316 views

Derivation of bound on expression involving binomial coefficient from Erdős and Rényi 1959

I'm in the process of working through Erdős and Rényi's 1959 article "On Random Graphs I". In the proof of the first Lemma, equation 14 gives a bound on an expression involving several binomial ...
1
vote
2answers
190 views

Proof $\binom{2\phi(r)}{\phi(r)+1} \geq 2^{\phi(r)}$

I try to proof the following $$\binom{2\phi(r)}{\phi(r)+1} \geq 2^{\phi(r)}$$ with $r \geq 3$ and $r \in \mathbb{P}$. Do I have to make in induction over $r$ or any better ideas? Any help is ...
1
vote
2answers
105 views

Showing that $ \prod\limits_{i=0}^{n} {n \choose i}\leq(\frac{2^n-2}{n-1})^{n-1} $

I would like to show that: $$ \prod_{i=0}^{n} {n \choose i}\leq \left(\frac{2^n-2}{n-1}\right)^{n-1} $$ $$n=2p $$ $$ \prod_{i=0}^{2p} {2p \choose i}=\prod_{i=1}^{2p-1} {2p \choose i}\leq {2p\choose ...
7
votes
4answers
370 views

Inequality with central binomial coefficients

For every even positive number $N$ we have: $$ {2N \choose N } < 2^N {N \choose N/2 } < 2 {2N \choose N } $$ (Furthermore, $\frac{2^N {N \choose N/2 }}{{2N \choose N }} \to \sqrt{2} $ for ...
1
vote
3answers
433 views

Binomial inequality

Show that we have: $$ \binom{n}{s}\leq n^n $$
9
votes
4answers
213 views

Bounding ${(2d-1)n-1\choose n-1}$

Claim: ${3n-1\choose n-1}\le 6.25^n$. Why? Can the proof be extended to obtain a bound on ${(2d-1)n-1\choose n-1}$, with the bound being $f(d)^n$ for some function $f$? (These numbers ...
6
votes
1answer
256 views

Inequality involving factorial

I am trying to prove following inequality: $$\binom{n}{k}<(en/k)^k$$ I tried Stirling approximation but I could not get anything further. Then I get $$\binom{n}{k}\approx \frac{\sqrt{2\pi ...