1
$\begingroup$

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.

  • 0
    @J.M.: Oh I see. That makes sense.2011-12-30

2 Answers 2

10

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

12

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$