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

I try to proof 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.

-
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$. –  Ｊ. Ｍ. Dec 30 '11 at 12:40
@J.M.: Oh I see. That makes sense. –  Paul Dec 30 '11 at 12:48

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$.

-

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$

-