Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|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
3  
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
2  
@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
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.