4
votes
2answers
73 views

Binomial expansion inequality

In a paper I am reading, there is a step that seems to come from the following inequality: $$(1+x)^\alpha \le 1+2^\alpha x,$$ where $0<x<1$. (Also, $3\le \alpha \le 9/2$ in the context of the ...
0
votes
2answers
67 views

Show that $\binom{n}{k}< \binom{n}{k+1}$ if and only if $k < (n-1)/2$ [closed]

Show that $\binom{n}{k} < \binom{n}{k+1}$ if and only if $k < \frac{n-1}{2}$ and then use this to deduce that the maximum of $\binom{n}{k}$ for $k=0,1,\dots,n$ is $\binom{n}{\lfloor ...
2
votes
0answers
30 views

Inequality in matroid theory

Working on a proof in matroid theory I found there is a smooth map from an open set of $(\mathbb{C}^{\ast})^{(d−1)(n−d−1)}$ to a disjoint union of tori $(S^{1})^{\binom{n}{d}-n}.$ As a direct ...
0
votes
2answers
55 views

Largest term in binomial expansion of $(1+n)^k$

The binomial expansion of $(1+n)^k$ is $$(1+n)^k=1+\binom{k}{1}n+\binom{k}{2}n^2+\cdots+\binom{k}{k}n^k.$$ If $n=1$, then the term in the middle is the largest, i.e. when $i=\lfloor k/2\rfloor$ and ...
1
vote
2answers
44 views

Let $C=\dfrac{1}{k}\left [\binom{2k-1}{k}-1 \right ]$ where $k \ge 3$. Show that $C\ge 3$.

I have a problem: Let $C=\dfrac{1}{k}\left [\binom{2k-1}{k}-1 \right ]$ where $k \ge 3$. Show that $C\ge 3$. Any help will be appreciated! Thanks!
2
votes
1answer
89 views

How prove this inequality $\frac{1}{n}\sum_{k=0}^{n-1}\binom{k}{a}\binom{k}{b}\le\frac{1}{a+b+1}\binom{n}{a}\binom{n}{b}$

let $a,b,n$ be positive integer numbers,and such $a,b\le n$, show that $$\dfrac{1}{n}\sum_{k=0}^{n-1}\binom{k}{a}\binom{k}{b}\le\dfrac{1}{a+b+1}\binom{n}{a}\binom{n}{b}$$ this inequality maybe ...
3
votes
1answer
44 views

How prove $\binom{n}{m}\le\left(\frac{en}{m}\right)^m$ [duplicate]

Show that $$\binom{n}{m}\le\left(\dfrac{en}{m}\right)^m$$ where $0<m\le n,m,n\in N^{+}$ My idea: since ...
2
votes
3answers
66 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
48 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
43 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
46 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 ...
1
vote
1answer
78 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?
11
votes
3answers
307 views

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

For any positive 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
54 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
51 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 ...
2
votes
1answer
83 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
45 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
46 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
55 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
38 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
200 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
97 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
64 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
226 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
482 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
252 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
249 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
230 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
213 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
195 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
542 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
111 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
144 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
84 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
224 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
411 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
263 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
157 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
119 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
305 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
291 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
324 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
193 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
109 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
394 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
457 views

Binomial inequality

Show that we have: $$ \binom{n}{s}\leq n^n $$