Property of Binomial Coefficient

I have a "must be trivial" problem which I could not solve.

Prove the following relation of binomial coefficients, if true: $$\sum_{k=1}^{n}{2n+1 \choose k}=2^{2n}-1$$

P.S. Though this is not homework, I appreciate any hints rather than explicit solutions.

I am looking for proofs from properties of binomial coefficients rather than other methods.

-

3 Answers

We have that $$\sum_{k=0}^{2n+1} \dbinom{2n+1}k = 2^{2n+1}$$ $$\sum_{k=0}^{n} \dbinom{2n+1}k + \sum_{k=n+1}^{2n+1} \dbinom{2n+1}k = 2^{2n+1}$$ Now note that $$\dbinom{2n+1}k = \dbinom{2n+1}{2n+1-k}$$ Hence, we get that $$2\sum_{k=0}^{n} \dbinom{2n+1}k = 2^{2n+1}$$ $$\sum_{k=0}^{n} \dbinom{2n+1}k = 2^{2n}$$ $$\dbinom{2n+1}0 + \sum_{k=1}^{n} \dbinom{2n+1}k = 2^{2n} \implies \sum_{k=1}^{n} \dbinom{2n+1}k = 2^{2n} - 1$$

-
Why are you in such a hurry to post the whole solution? –  007resu Jan 6 '13 at 20:16

Substitute $x=1$ into $(1+x)^{2n+1}=\sum_{k=0}^{2n+1}\binom{2n+1}{k}x^k$ to obtain $2^{2n+1}=\sum_{k=0}^{2n+1}\binom{2n+1}{k}=2\sum_{k=0}^{n}\binom{2n+1}{k}$ since $\binom{2n+1}{k}=\binom{2n+1}{2n+1-k}$.

-

Use this result (Binomial Theorem) $$(a + b)^n = \sum_{k=0}^n {n\choose k} a^k b^{n-k}.$$

-