All Questions
82
questions
0
votes
1
answer
34
views
How to Derive the Binomial Coefficient Upper Bound and Final Inequality in "Scheduling Multithreaded Computations by Work Stealing"?
In the paper Scheduling Multithreaded Computations by Work Stealing under the section "Atomic accesses and the recycling game", it mentions the binomial coefficient approximation:
$$ \binom{...
- 3
5
votes
3
answers
132
views
Strengthening the Log-Concavity of Binomial Coefficients: $\binom{n}{k-1}\binom{n}{k+1} < \binom{n}{k}^2 - \binom{n}{k}$
In the following question:
Log concavity of binomial coefficients: $ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $
It is proven via a combinatorial injective argument.
However, by noticing that ...
- 4,394
2
votes
0
answers
132
views
how to prove $\sum_{j=\frac{k}{2}+1}^{k-1}\binom{k-1}{j}\binom{n-(k-1)}{k-j}<2\binom{n-1}{k-1}$?
I want to prove for $2\le k<n$ (and $k$ is even if necessary)
$$\sum_{j=\frac{k}{2}+1}^{k-1}\binom{k-1}{j}\binom{n-(k-1)}{k-j}<2\binom{n-1}{k-1}.$$
MATLAB verifies it is true when $n=30$ and $k=...
- 2,075
0
votes
1
answer
56
views
How to get this lower bound for $C(m^2,m-1)$?
While applying Nechiporuk’s Theorem to get a lower bound on the formula size of Element distinction function, the following inequality is used: (ref here)
$C(m^2,m-1) \geq (m^2-m+1)^{m-1}$.
Is there a ...
- 214
3
votes
1
answer
110
views
Alternative proof for ${pn \choose n}{qn \choose n} \ge {pqn \choose n}$ inequality
Reading this question, I saw that for $p,q,n$ positive integers the following inequality holds:
$${pn \choose n}{qn \choose n} \ge {pqn \choose n}$$
The inequality is not tight.
A simple combinatorial ...
- 2,103
3
votes
3
answers
313
views
Good upper bound on ratio of binomial coefficients
What is the asymptotic behavior of $n/2+k/2 \choose k$/$n\choose k$ for $k\le n/2$. Can we show that it goes down (sub)exponential in $k$ i.e. $n/2+k/2 \choose k$/$n\choose k$ $\le c^{-k^{\epsilon}}$ ...
- 1,693
2
votes
0
answers
81
views
Inequality of Narayana numbers
In some computations I am making, it is desirable to deduce that a certain expression is positive. I managed to rewrite it in terms of Narayana numbers, which are defined by $N(n,i) := \frac{1}{n}\...
- 713
3
votes
3
answers
126
views
Prove that $\binom{13+m}{m}-(m+1)\binom{6+m}{m}\geq m$ for $m\in \mathbb{N}\backslash \{0,1\}$
Prove the following inequality for every $m\in \mathbb{N}\backslash \{0,1\}$:
$$ \binom{13+m}{m}-(m+1)\binom{6+m}{m}\geq m.$$
By some computational arguments, the inequality seems to be true and in ...
- 185
1
vote
1
answer
56
views
proving an inequality based on double products and binomial
Iv been trying to prove the following inequality: let $a_1,\ldots,a_n$ be a non-increasing sequence, i.e., $a_1\geq a_2\geq \cdots \geq a_n\geq 0$ such that $\sum_i a_i=m$. Then, prove that
$$\prod_{i=...
- 413
0
votes
0
answers
53
views
Hints and tips to prove this inequality.
Let's say that $n = \lfloor{2^{\frac{k}{2}}}\rfloor$ for some integer $k \geq 3$. I need to prove this inequality:
$${n \choose k}\cdot2^{1-{k \choose 2}} < 1$$
I tried to rewrite those terms or ...
- 43
4
votes
1
answer
69
views
For $n \geq 2$, show that $\sum_{r = 1}^{n} r \sqrt{\binom{n}{r}} < \sqrt{2 ^ {n - 1} n ^ 3}$
Good day,
Can someone help me with giving hints for this problem:
Show that for $n \geq 2, n \in \mathbb{Z}$, $$\sum_{r = 1}^{n} r \sqrt{\binom{n}{r}} < \sqrt{2 ^ {n - 1} n ^ 3}$$
I tried $$\sum_{...
- 1,858
1
vote
0
answers
92
views
Summing binomial coefficients and manipulating summation order
I'm having trouble understanding Example 3 (pg. 61).
As a preliminary, the solution makes use of the following two identities, which I've restated below for convenience:
Eq. (25) on pg. 59:
$$\sum_{k=...
- 673
5
votes
2
answers
258
views
More elegant proofs of $\binom a2+\binom b2\leq \binom{a+b-1}2$
I came to know about the inequality
$$\binom a2+\binom b2\leq \binom{a+b-1}2$$
and tried to prove it.
It was quite easy to derive it using brute force algebraic calculations. All boils down to showing
...
- 9,592
3
votes
1
answer
129
views
Where does this inequality come from?
In Bollobás's Modern Graph Theory, section IV.4, Page 120 line -10, he uses the inequality
$$\frac{t {n \choose t}}{n {\epsilon n \choose t}} \leq \frac{t}{n} \epsilon^{-t} (1-\frac{t}{\epsilon n})^{-...
- 467
13
votes
1
answer
614
views
Inequality between binomial sums
I want to prove that the following inequality holds whenever $k\leq n-1$ and $1\leq i\leq \lfloor\frac{k}{2}\rfloor$.
$$\frac{2}{C}\binom{n}{k}\binom{k}{i+1} \leq \frac{k}{i}\sum_{j=i}^{k-1}
(k-j)\...
- 713