Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I try to prove the following

$$\binom{2\phi(r)}{\phi(r)+1} \geq 2^{\phi(r)}$$

with $r \geq 3$ and $r \in \mathbb{P}$. Do I have to make in induction over $r$ or any better ideas?

Any help is appreciated.

share|cite|improve this question
Does $\mathbb{P}$ mean the set of all natural numbers/positive integers? Normally we denote it by $\mathbb{N}$ or $\mathbb{Z}^+$. Also, $\phi(r)$ is the Euler's phi function, right? – Paul Dec 30 '11 at 12:31
The given inequality only depends on $r$ in the sense that it depends on $\varphi(r)$. It might be worthwhile to try to show (or find a counterexample) that $\binom{2n}{n+1}\geq 2^n$ for $n\geq 2$. – Aaron Dec 30 '11 at 12:33
@Paul: I took it to mean the set of primes, in which case $\phi(p)=p-1$. – J. M. Dec 30 '11 at 12:40
@J.M.: Oh I see. That makes sense. – Paul Dec 30 '11 at 12:48
up vote 10 down vote accepted

Let $x_n=2^{-n}{2n\choose n+1}$. Then $x_{n+1}=x_n\frac{(2n+1)(n+1)}{n(n+2)}\gt x_n$ for every $n\geqslant1$ and $x_2=1$, hence $x_n\geqslant1$ for every $n\geqslant2$.

Since $\varphi(r)\geqslant2$ for every integer $r\geqslant3$, the estimate above implies that the desired inequality holds for every (not necessarily prime) integer $r\geqslant3$.

share|cite|improve this answer

Combinatorial proof of ${2n \choose n+1} \geq 2^n$ where $n \geq 2$:

Let's take set $\{x_1,y_1,\dots,x_{n-2},y_{n-2},a,b,c,d\}$ which has $2n$ elements; select three elements out of $\{a,b,c,d\}$ and for all $i$, a single element of $\{x_i,y_i\}$, you'll select $n+1$ in total. So

${2n \choose n+1} \geq {4 \choose 3} 2^{n-2}=2^n$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.