2
votes
2answers
50 views

The smallest $n$ for which the sum of binomial coefficients exceeds $31$

I have a problem with the binomial theorem. What is the result of solving this inequality: $$ \binom{n}{1} + \binom{n}{2} + \binom{n}{3} + \cdots +\binom{n}{n} > 31 $$
0
votes
1answer
39 views

A counting problem on the integer lattice

Let $K$ be a subset of the integer lattice $\mathbb Z^2$such that it contains elements of the form $k=(k_1,k_2) $ where $k_1,k_2$ are integers and $k_2\neq 0$. Find $m$, an integer if possible, such ...
2
votes
2answers
59 views

The sum of binomial coefficients up to $k\le n/3$ does not exceed the $k$th coefficient

How would you prove the following (for when $k\leq\frac{n}{3}$)? $$\sum_{i=0}^{k-1} \binom ni \le \binom nk$$
1
vote
1answer
65 views

Prove $1! + 2! + . . . + n! < (n + 1)!$ using mathematical induction [duplicate]

$1! + 2! + . . . + n! < (n + 1)!$ This question has left me stumped for quite some time. I am not sure how to approach it. (I am really bad at induction).
0
votes
1answer
26 views

Chong inequalites about permutations

I read about two inequalities called Chong's inequalities. They state: $$\sum_{k=1}^N\dfrac{a_k}{a_{\pi(k)}}\ge N$$ and $$\displaystyle\prod_{k=1}^Na_k^{a_k}\ge\prod_{k=1}^N a_k^{a_{\pi(k)}}$$ I ...
0
votes
2answers
71 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 ...
1
vote
3answers
39 views

Greatest value of the binomial coefficient. [duplicate]

How should I prove the greatest value of the binomial coefficient $C(n,r)$ occurs for $r=\left[\cfrac{(n+1)}{2}\right]$ ?
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
36 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
4answers
145 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 ...
2
votes
3answers
42 views

Number of positive integral solutions

Find the number of Positive integral solutions of $$15<x_1+x_2+x_3 \le20$$ Now, I know the formulae for similar problems without the inequality. However, I want to understand the basic concept or ...
9
votes
1answer
166 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
188 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
67 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
305 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
95 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
191 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
42 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 ...
4
votes
3answers
166 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
48 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
86 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
73 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
65 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
121 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
76 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
29 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
144 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
93 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
246 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
2answers
138 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
89 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
43 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
120 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
512 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
374 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
235 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
49 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
250 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
65 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
177 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
293 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
114 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 ...
13
votes
3answers
392 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
77 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
180 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
111 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$ ...