8
$\begingroup$

I'm trying to prove the following equation above. So far I have: \begin{align} 2^{2n} &= (1+1)^{2n}\\ &= \sum_{k=0}^{2n}\binom{2n}{k}1^k1^{n-k} = \sum_{k=0}^{2n}\binom{2n}{k} & \text{(By the Binomial Theorem)} \end{align}

I know I have to use the following identity somehow: $$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$$

How do I split my summation to get what I'm looking for? Thanks!

EDIT: HERE IS MY SOLUTION \begin{align*} 2^{2n} &= (1+1)^{2n}\\ &= \sum_{k=0}^{2n}\binom{2n}{k}1^k1^{2n-k} & \text{(By the Binomial Theorem)}\\ &= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=n+1}^{2n}\binom{2n}{k}\\ &= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=n+1}^{2n}\binom{2n}{2n-k} & \text{(Binomial Symmetry)}\\ &= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=0}^{n-1}\binom{2n}{k}\\ &= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=1}^{n}\binom{2n}{k-1}\\ &= \binom{2n}{0} + \sum_{k=1}^{n}\binom{2n}{k} + \sum_{k=1}^{n}\binom{2n}{k-1}\\ &= \binom{2n}{0} + \sum_{k=1}^{n}\binom{2n+1}{k} & \text{(By Identity listed above)}\\ &= \sum_{k=0}^{n}\binom{2n+1}{k} \end{align*}

$\endgroup$
  • 2
    $\begingroup$ Hint: Add in the missing second half, from $n+1$ to $2n+1$. We do not need the identity you quoted. $\endgroup$ – André Nicolas Sep 20 '15 at 17:05
5
$\begingroup$

$$\sum_{k=0}^{n}\binom{2n+1}{k}=\frac{1}{2}\sum_{k=0}^{2n+1}\binom{2n+1}{k}=\frac{2^{2n+1}}{2}=2^{2n}$$

Using the relation $$\binom{2n+1}{k}=\binom{2n+1}{2n+1-k}$$ for $0 \le k \le n$.

$\endgroup$
  • $\begingroup$ I'm confused how you can just change the upper bound of the summation like that. $\endgroup$ – plast Sep 20 '15 at 17:37
  • $\begingroup$ I added a relation used to get the equality of the sums. $\endgroup$ – mathcounterexamples.net Sep 20 '15 at 17:43
4
$\begingroup$

$$ 2^{2n}=\frac12\cdot 2^{2n+1}=\frac12\sum_{k=0}^{2n+1}{2n+1\choose k}=\frac12\sum_{k=0}^n\left({2n+1\choose k}+{2n+1\choose 2n+1-k}\right)$$

$\endgroup$
1
$\begingroup$

I would suggest to use induction:

For $n=1$:

$2^2 = \binom{3}{0}+\binom{3}{1}$, true.

For $m=n+1$:

$2^{2n+2}=4\cdot 2^{2n} = \sum_{k=0}^{n}\binom{2n+1}{k} + \binom{2n+2}{n+1} = 2^{2n} + \binom{2n+2}{n+1} = 2^{2n} + \frac{(2n+2)!}{(n+1)!^2}$

$\endgroup$
  • $\begingroup$ ...well, something won't work, I am thinking on it. $\endgroup$ – peterh Sep 20 '15 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.