0
votes
0answers
17 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
79 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 ??
0
votes
0answers
27 views

Proving Inequality Equation with $4$ variables [on hold]

How would I approach this question? Let $a, b, x, y$ be positive numbers satisfying: $$a*x ≤ 100,\ b*x ≤ 100,\ a*y ≤ 100,\ b*y ≤ 50$$ Prove that $a*x+b*x+a*y+b*y ≤ 300$.
2
votes
1answer
142 views
+50

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
36 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 ...
0
votes
1answer
44 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
39 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
84 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
65 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
56 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
102 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
68 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$
1
vote
0answers
85 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
240 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
96 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
30 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
95 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
477 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
366 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
199 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
45 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
231 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
62 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
267 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
102 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
110 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
324 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
178 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
79 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
102 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
127 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
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
360 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
847 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 + ...
7
votes
1answer
353 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
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 ...
2
votes
2answers
220 views

A combinatorial inequality

How can I prove $$ \log \binom nk \leq k \left(1 +\log\frac{n}{k}\right) $$ where $\binom\cdot\cdot$ stands for combination. I tried to use stirling approximation but I couldn't get the inequality.
3
votes
1answer
400 views

Equidistant Points in the Plane problem by Paul Erdos

This problem was actually posed by Erdos in Geombinatorics (Oct. 1994) and goes as follows: Let $f(n)$ be the largest integer for which there are $n$ distinct points $x_1,x_2,\dots,x_n$ in the plane ...
-1
votes
2answers
129 views

how to prove an integer inequality

Given a positive integer $n$, is there a simple way to see that $$ (n+3)^{n+2}(2n+5)^{n+2}(n+1)^{n+2}(2n+1)^n \ge (n+2)^{2n+4}(2n+3)^{2n+2} $$ Any hint is welcome.
1
vote
0answers
225 views

Inequality with Stirling's numbers

I supect that for all $n>k>0$: $k^2\left\{ \begin{array}{c}n\\k\end{array} \right\}^2 +2k\left\{ \begin{array}{c}n\\k\end{array} \right\}\left\{ \begin{array}{c}n\\k-1\end{array} ...
6
votes
4answers
262 views

How many sequence of integers ($j_1 , j_2 , . . . , j_k$) are there such that $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$?

I need to solve the problem, How many sequence of integers ($j_1 , j_2 , . . . , j_k$) are there such that $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$? I've been given a hint, (Hint: Reduce the ...
0
votes
1answer
33 views

If we define the expression $P(x)=x^2$ and an expression $Q(x) = |4x|$, then for how many integer values is $P(x) -Q(x)$ a positive quantity?

If we define the expression $P(x)=x^2$ and an expression $Q(x) = |4x|$, then for how many integer values is $P(x) -Q(x)$ a positive quantity? $ a)2 \quad\quad\quad b) 4 \quad\quad c) 6 ...
2
votes
1answer
125 views

Bounding the number of integer solutions of the following inequality

Let $r\geq 1$ be a real number, $-1\leq x\leq 1$ a real number and $y>2$ a real number. We consider this data to be fixed. How can I obtain an upper bound on the number of $(a,b,c,d)\in ...