# Proofs from the BOOK: Bertrand's postulate: $\binom{2m+1}{m}\leq 2^{2m}$

I have a very hard proof from "Proofs from the BOOK". It's the section about Bertrand's postulate, page 8:

It's about the part, where the author says:

$$\binom{2m+1}{m}\leq 2^{2m}$$ because $\binom{2m+1}{m}=\binom{2m+1}{m+1}$ are the same in $\sum \limits_{k=0}^{2m+1} \binom{2m+1}{k}=2^{2m+1}$

I see, why they are the same, but I don't see the reason to say $\binom{2m+1}{m}\leq 2^{2m}$. Any help would be fine :)

-

The sum is essentially $a_1 + a_2 + ... +a_m + a_{m+1} + ... + a_{2m+1} = 2^{2m+1}$, (where $a_k$ is shorthand for $\binom{2m+1}{k}$) since everything is non-negative, we can say $a_m + a_{m+1} \leq a_1 + a_2 + ... +a_m + a_{m+1} + ... + a_{2m+1} = 2^{2m+1}$ and from the equality we know $a_m = a_{m+1}$. Putting it all together:

$a_m + a_{m+1} = 2a_m \leq 2^{2m+1}$ therefore $a_m \leq 2^{2m}$

-

$\binom{2m+1}{m}+\binom{2m+1}{m+1}\leq 2^{2m+1}$ (follows from binomial formula)

But the coefficients are the same, so

$2\binom{2m+1}{m}\leq 2^{2m+1}$

-

Since $2m+1$ is odd, there will be an even number of coefficients (since you have everything from $\binom{2m+1}{0}$ to $\binom{2m+1}{2m+1}$). Because the coefficients are symmetric, you can write:

$\sum \limits_{k=0}^{m} \binom{2m+1}{k}=\sum \limits_{k=m+1}^{2m+1} \binom{2m+1}{k}$

But $\sum \limits_{k=0}^{2m+1} \binom{2m+1}{k}=\sum \limits_{k=0}^{m} \binom{2m+1}{k} + \sum \limits_{k=m+1}^{2m+1} \binom{2m+1}{k}=2^{2m+1}$

$2 \times \sum \limits_{k=0}^{m} \binom{2m+1}{k} = 2^{2m+1}$

$\sum \limits_{k=0}^{m} \binom{2m+1}{k} = 2^{2m}$

Since $\binom{2m+1}{m}$ is part of the sum $\sum \limits_{k=0}^{m} \binom{2m+1}{k}$, it follows that $\binom{2m+1}{m}\leq 2^{2m}$, equality when $m=0$

-
and when m is not 0? –  ulead86 Nov 10 '11 at 15:39
Then $\binom{2m+1}{m} < 2^{2m}$ –  Sp3000 Nov 11 '11 at 1:52