1
$\begingroup$

Let $\epsilon$ and $t$ be fixed numbers with $t$ and integer. I came across the following inequality in a counting problem. $$n\binom{\epsilon n}{t}>t\binom{n}{t}.$$ I want to show that for $n$ large enough this inequality is true. I don't know if my hypothesis is true or not. I've made many lists in mathematica with different $\epsilon$ and $t$. All of the lists showed my hypothesis was correct in that case. Any ideas on how to prove this result? Any much appreciated.

$\endgroup$
2
  • 1
    $\begingroup$ I think you used the wrong inequality in the question and the right inequality in the title. $\endgroup$
    – G. Bach
    Apr 23, 2014 at 0:43
  • $\begingroup$ @G.Bach They both were wrong. Thank you for the catch. $\endgroup$ Apr 23, 2014 at 0:49

2 Answers 2

2
$\begingroup$

Intuitively, the left hand side grows linearly in $n$ and has a bigger binomial for any $n \in \mathbb{N}$ (since $\binom{n}{c} \geq \binom{m}{c}$ for any $c$ and $n\geq m$). Formally:

$$n\binom{\epsilon n}{t}= n \frac{(\epsilon n) ^{\underline t}}{t!}$$

and

$$t\binom{n}{t}= t \frac{n ^{\underline t}}{t!}$$

we get

\begin{align} n\binom{\epsilon n}{t} &> t\binom{n}{t} \\ \iff n \cdot (\epsilon n) ^{\underline t} &> t \cdot n ^{\underline t} \end{align}

Due to the monotonicity of the falling factorial for any $t \geq 0$, $\epsilon n \geq n$ and $n > t$ for large $n$, your inequality follows.

(All this is assuming that $\epsilon \in \mathbb{N}, n, t, c \in \mathbb{N_0}$.)

$\endgroup$
3
  • $\begingroup$ $n$ and $t$ are natural. $\epsilon$ is real. Your answer was enough to get me there. $\endgroup$ Apr 23, 2014 at 4:17
  • $\begingroup$ @TheNumber23 I'd be interested to see the proof for real $\epsilon$. $\endgroup$
    – G. Bach
    Apr 23, 2014 at 11:45
  • $\begingroup$ You can just replace $\epsilon n$ with $\lfloor\epsilon n\rfloor$. Since $\binom{m}{t}$ is increasing as $m$ increases. Or you can do the approximation I did below. $\endgroup$ Apr 23, 2014 at 21:52
0
$\begingroup$

Let $\epsilon>0$ and $n,t\in\mathbb{N}$. Assume for sake of contradiction that for all $n$ $$n\binom{\epsilon n}{t}\leq t\binom{n}{t}.$$ Then that would yield $$ \binom{\epsilon n}{t}/\binom{n}{t}\leq \dfrac{t}{n}.$$ for all $n$. Using the appropriate approximations from this wikipedia page http://en.wikipedia.org/wiki/Binomial_coefficient We have $$ \dfrac{\epsilon^{t}}{t^{t}t!}\leq \dfrac{t}{n}$$ for all $n$ which is clearly false because $\epsilon $ and $t$ are fixed.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .