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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Paul
    Dec 30, 2011 at 12:31
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Aaron
    Dec 30, 2011 at 12:33
  • 2
    $\begingroup$ @Paul: I took it to mean the set of primes, in which case $\phi(p)=p-1$. $\endgroup$ Dec 30, 2011 at 12:40
  • $\begingroup$ @J.M.: Oh I see. That makes sense. $\endgroup$
    – Paul
    Dec 30, 2011 at 12:48

2 Answers 2

13
$\begingroup$

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$

$\endgroup$
10
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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