0
votes
2answers
69 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 ...
0
votes
1answer
36 views

How to get n from n-1

I know this question is probably trivial, but I'm having great difficulty with it for some reason. So, I want to solve for $p$: $n-1 \geq 2(n-p)$ I know that the answer is $n \leq 2p -1 ...
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 ...
2
votes
3answers
119 views

Log concavity of binomial coefficients: $ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $

How do we prove that Binomial coefficients are log-concave? A sequence $a_0, \dots, a_n$ is log-concave if $a_k^2 \geq a_{k-1}a_{k+1}$. $$ \binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1} $$ If $ n ...
8
votes
1answer
142 views

One-Line Proof for $n! \geq (\frac n e)^n$

I was told to find a one-line proof for $n! \geq (\frac n e)^n$. I'm advised that Stirling's formula is not helpful. I've spent a little bit of time on it, but the solution is not coming to me. I feel ...
11
votes
4answers
182 views

How find this minimum of the value $f(1)+f(2)+\cdots+f(100)$

Give the positive integer set $A=\{1,2,3,\cdots,100\}$, and define function $f:A\to A$ and (1):such for any $1\le i\le 99$,have $$|f(i)-f(i+1)|\le 1$$ (2): for any $1\le i\le 100$,have ...
0
votes
2answers
64 views

number of positive integer solution of inequation

Given an inequation with P,Q,R all integers, $P \cdot R \cdot b + P \cdot Q \cdot c - Q \cdot R \cdot a \geq 0$ how many positive integer solutions of $(a, b, c)$ ? Here $a \leq P, b \leq Q, c \leq ...
7
votes
1answer
302 views

How to prove this sequence of inequalities

The number $c_{g}(n)$ is defined by the recurrence \begin{equation} c_{g}(n) = c_{g}(n-1)+ (n-1)(n-2)c_{g-1}(n-2) , \end{equation} with $c_{0}(n)=1$ for any $n\geq 1$ and $c_{g}(n)=0$ if $n \leq 2g$. ...
4
votes
2answers
92 views

Prove that ax+bx+ay+by ≤ 300.

Let $a,b,x,y$ be positive numbers satisfying: $ax ≤ 100, bx ≤ 100$, $ay ≤ 100, by ≤ 50$. Prove that $ax+bx+ay+by ≤ 300$. Can someone help me ??
4
votes
1answer
187 views

How prove this $|S_{1}|-|S_{2}|\le 2^{2n}\binom{2n}{n}$

Question: Let $n\in \mathbf N^{+}$,and define set $S=\{1,2,\cdots,4n\}$, for any $ a<b\in \mathbf R^{+}$, define $$S_{1}=\{\,X\mid X\subseteq S,a\le S(X)\le b,S(X)\equiv 1\pmod 2\,\}$$ ...
0
votes
2answers
40 views

Solving Problem by different Method ( non-induction)

I have this problem , which I was able to prove it by induction, but I wonder could be solve by direct method ( for example combinatorial method). I want to find number of solution for $$0 \le ...
3
votes
3answers
123 views

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac n2 \rceil$ or $ \lfloor \frac n2\rfloor $?

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac{n}{2} \rceil $ or $ \lfloor \frac{n}{2} \rfloor$ ? This link provides a proof of sorts but it is not satisfying. From what I ...
0
votes
1answer
45 views

Inductive proof for the inequality

I would prove that $n^2<2^{n+1}$ for all natural numbers by induction proof. How ?
0
votes
2answers
45 views

Combinatorial Inequality

For any integer $n>1$ prove that, $$\large 2^n < {2n \choose n} < \frac{2^n}{\prod^{i=n-1}_{i=0}(1-\frac{i}{n})}$$ Now proving that the first term is smaller than the third term is ...
1
vote
3answers
85 views

To prove the inequality

$${n \choose 0}+{n \choose 3}+{n \choose 6}+\cdots+{n \choose 3k}\le \dfrac13(2^n+2)$$ Where $3k\le n$ It looks similar to the expansion of $2^n$ and since every three terms is missing 2 so the ...
2
votes
1answer
70 views

Range of inner product of a sequence and its permutation

$a^n :=(a_i)_1^n$ is a finite sequence of real numbers of length $n$, where $\sum\limits_{i=1}^n a_i=0$ and $\sum\limits_{i=1}^n a_i^2=1$. Consider $s_n(a^n,\sigma):=\sum\limits_{i=1}^n ...
0
votes
3answers
62 views

combinatorics - how many integer solutions

simple question. we are given this equation $x_1+x_2+x_3+x_4=17$ when: $0\leq x_2\leq 7$, $0\leq x_3 \leq 13$ $0\leq x_4 \leq 13$ and for all $i$: $x_i \in \mathbb Z$ we are asked how many ...
3
votes
1answer
118 views

Show that $\frac1{\sqrt{(n+\frac12) \pi}} \le\frac{1\cdot 3\cdot 5 … (2n-1)}{2\cdot 4\cdot 6 … (2n)} \le \frac1{\sqrt{n \pi}} $

Show that, if $n$ is a positive integer, $$\frac1{\sqrt{(n+\frac12) \pi}} \le\frac{1\cdot 3\cdot 5 ... (2n-1)}{2\cdot 4\cdot 6 ... (2n)} \le \frac1{\sqrt{n \pi}} . $$ This result is in a current ...
1
vote
1answer
73 views

Pigeonhole Principle question - sum of positive integers

A question that should be solved with pigeonhole but I'm having problems. $a_1,a_2,a_3,...,a_{77}$ are positive integers. We are given that $a_1+a_2+a_3+...+a_{76}+a_{77} < 133$ Show that there ...
0
votes
1answer
28 views

combinatory question…

Any idea for this question: Let $ 0<i<\delta n$ where $0<\delta \le 1-q^{-1}$ and $ q\ge 2$. prove that $ n\choose {i-1}$ $\times (q-1)^{i-1} <$$ n \choose i$$(q-1)^i$
2
votes
1answer
135 views

LYM Inequality question

Suppose that $F ⊂ P(n)$ is a set system containing no chain with $k + 1$ sets. Prove that $\sum\limits_{r=1}^n \frac{|F_{r}|}{n \choose r} ≤ k$, where $F_{i} = F \cap [n]^{(i)}$ for each i. ...
1
vote
0answers
92 views

Is there such an example?

Is there an example of a sequence of point sets $\left\{ S_{n}\right\} _{n=1}^{\infty}$in which $S_{n}$ is a set of $n$ points inside the unit triangle, such that the minimum altitude of the triangles ...
4
votes
1answer
243 views

How prove this$\frac{1}{P_{0}P_{1}}+\frac{1}{P_{0}P_{2}}+\cdots+\frac{1}{P_{0}P_{n}}<\sqrt{15n}$

Let $P_{0},P_{1},P_{2},\cdots,P_{n}$ be $n+1$ points in the plane. Let $ d=1$ denote the minimal value of all the distances between any two points. Prove that ...
1
vote
1answer
98 views

How find this maximum of $P_{1}+P_{n}$

Question $n$ students attend a test of $m$ problems where $m, n \ge 2$. The scoring rule for each problem is: If $x$ students answer a problem incorrectly, then a correct answer worth $x$ points ...
1
vote
1answer
88 views

Proof of Nonnegativity Inequality

Prove the Inequality: $$\sum_{i,j}\left ( (PAQ)_{i,j}\frac{B_{i,j}^2}{A_{i,j}}- (PBQ)_{i,j}B_{i,j}\right ) \geqslant 0$$ Given that: $P$ and $Q$ are $n$x$n$ and $m$x$m$ symmetric matrices, $A$ ...
1
vote
1answer
34 views

Cardinality of Solutions to an Inequality [duplicate]

Show that the number of solutions in nonneg. int. of the ineq. $$x_1+x_2+\cdots +x_n\leq M,$$ where $M$ is a nonneg. int., is $C(M+n,n)$.
-2
votes
2answers
106 views

$x_1+x_2+\cdots+x_n\leq M$: Cardinality of Solution Set is $C(M+n, n)$

Show that the number of solutions in nonnegative integers of the inequality $$x_1+x_2+\cdots+x_n\leq M,$$ where $M$ is a nonnegative integer, is $C(M+n, n)$.
12
votes
7answers
486 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 ...
4
votes
1answer
371 views

Conjecture regarding trapping rational numbers in some special intervals

Conjecture: Let $b\in\mathbb{N}_{\geq3}$ and $\{x_i\}$ be a collection of $b−2$ rational numbers greater than $1$. Does there always exist a natural number $a$ such that for all $i$ there exists some ...
1
vote
0answers
218 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 ...
4
votes
1answer
48 views

Combinatorics question about addition

I noticed the following happening and I wonder if it can be proved: Assume $x_1, \ldots, x_n$ are positive integers and $h$ is their least common multiple. Now assume $$a_1x_1 + \cdots a_nx_n > ...
1
vote
1answer
48 views

Counting problem - How many times an inequality holds?

Let $k>2$ be a natural number and let $b$ be a non-negative real number. Now, for each $n$, $m \in \{ 1, 2, ... k \}$, consider the following inequalities: $$ mb < k - n $$ We have $k^2$ ...
2
votes
0answers
238 views

Find a tight upper bound of the following expectation.

I am stuck in finding a tight upper bound (as tight as possible) of the following expectation $$E\left [ (1-a\cdot b^{X})^{m} \right ]$$ where $X\sim B(n-1,p)$ is a binomial random variable.In ...
0
votes
0answers
63 views

proving an inequality by induction

Not sure how to proceed. I'm trying to prove that the following inequality is true. I know that $t_2 = 6$ and $t_3=17$ from the problem statement. The base case is obvious. $t_{r+1} \leq (r+1) (t_r ...
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 ...
7
votes
1answer
282 views

On Magnitudes of Sums of Roots of Unity and a Simple Trigonometric Inequality

The Problem Let $r,q,m$ be positive integers such that $4 \leq r$ and $1<m,q\leq r/2$. Is it the case that $$\left | \sum_{k=0}^{q-1} \zeta^{km}\right | < \left |\sum_{k=0}^{q-1} ...
1
vote
3answers
104 views

bound for the product of numbers

Let $n \in N$. Fix $m \in [-n,n]$. I am curious, how to bound from above the following expression $$ (n-m)^{\frac{n-m}{2}+1}(n+m)^{\frac{n+m+1}{2}}\leq \quad ? $$ Thank you.
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 ...
11
votes
2answers
332 views

Find the number of pairs $(m, n)$ of positive integers such that $\frac{ m}{n+1} < \sqrt{2} < \frac{m+1}{n}$

Find the number of pairs $(m, n)$ of positive integers such that $\frac{ m}{n+1} < \sqrt{2} < \frac{m+1}{n}$ Constraint: $m$ and $n$ are both less than or equal to 1000 I toiled over this ...
4
votes
1answer
76 views

inequality with numbers--when its true?

Help me please to understand when the inequality true. Let $n<N,$ where $n, N$ are natural numbers. For which $n$ and $N$ the following is true $$ n^{2n+1}\leq N^{N+1}? $$ Thank you.
1
vote
0answers
179 views

Does this hold?

Strayed on the following question. Assume that $x_{1}$,$\ldots$, $x_{d}\ge0$ with $x_{1}+\ldots+x_{d}=1$ and $y_{1},\ldots,y_{d}\in\mathbb{R}$. Does $$ \min_{1\le i\ne j\le ...
-1
votes
1answer
80 views

Count the number of integer solution to $\sum_{i=1}^ {4}{a_i\times b_i} \geq 8 $? [closed]

Count the number of integer solution to $\sum_{i=1}^ {4}{a_i\times b_i} \geq 8 $ such that condition 1: $1 \leq a_i \leq 7$ condition 2: $1 \leq b_i \leq 4$ condition 3: $\sum_{i=1}^{4} {a_i} = ...
0
votes
1answer
108 views

Count the number of integer solution to $\sum_{i=1}^ {2}{a_i\times b_i} \geq 6 $ [closed]

Count the number of integer solution to $\sum_{i=1}^ {2}{a_i\times b_i} \geq 6 $ such that condition 1: $1 \leq a_i \leq 7$ condition 2: $1 \leq b_i \leq 4$ condition 3: $\sum_{i=1}^{2} {a_i} = 8$ ...
0
votes
2answers
85 views

Counting $2010^2$-tuples

Here's a problem i invented myself, but i'm not sure about my solution. I'll show it later, so people can enjoy trying to find one: Consider the function $f:\mathbb{R}^2\to\{1,2,...,2012\}$ that ...
3
votes
1answer
131 views

An inequality involving Stirling numbers of the second kind

The task is to prove the following inequality: $\begin{Bmatrix} mn\\ n \end{Bmatrix} \geqslant \frac{(mn)!}{(m!)^nn!}$ , where $m, n \in \mathbb{N_+}$ and to determine when the equality ...
4
votes
1answer
226 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
415 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
3answers
979 views

Count the number of solutions of the inequality $x + y + z \leq N$

Problem Given $A, B, C $ and $N$. How many integer solutions are there of the following inequality: $$x + y + z \leq N$$ where $0 \leq x \leq A, 0 \leq y \leq B, 0 \leq z \leq C$? When $A + ...
8
votes
1answer
379 views

Putnam PigeonHole

This is from page 12 of Putnam and Beyond. Problem: Prove that for every set $X ={x_1,x_2, \ldots ,x_n}$ of $n$ real numbers, there exists a nonempty subset $S$ of $X$ and an integer $m$ such that ...
1
vote
3answers
158 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 ...