# Thread: Combinatorics - identity: sum[0<=k<=n/2](-1)^k binom(n-k,k) 2^(n-2k) = n+1 ...?

1. ## Combinatorics - identity: sum[0<=k<=n/2](-1)^k binom(n-k,k) 2^(n-2k) = n+1 ...?

Maybe can someone help? Is the equation with n ≥ 0 correct? (easier to solve by using generating function)

$\displaystyle \mbox{2. }\quad \sum_{0\leq k \leq n/2}\, (-1)^k\, \binom{n\, -\, k}{k}\, 2^{n-2k}\, =\, n\, +\, 1\quad ?$

$\displaystyle \mbox{3. }\quad \sum_{k=0}^{n}\, \binom{n\, +\, k}{2k}\, 2^{n-k}\, =\, \dfrac{2^{2n+1}\, +\, 1}{3}\quad ?$

$\displaystyle \mbox{4. }\quad \sum_{k=0}^n\, \binom{2k}{k}\, \binom{n}{k}\, \left(-\dfrac{1}{4}\right)^k\, =\, 2^{-2n}\, \binom{2n}{n}\quad ?$

$\displaystyle \mbox{5. }\quad \sum_k\, \binom{m}{k}\, \binom{n\, +\, k}{m}\, =\, \sum_k\, \binom{m}{k}\, \binom{n}{k}\, 2^k\quad ?$

. . . . .$\mbox{Here }\, \binom{n}{k}\, = 0\, \mbox{ if }\, k\, >\, n.$

2. Originally Posted by evebart
Maybe can someone help? Is the equation with n ≥ 0 correct? (easier to solve by using generating function)

$\displaystyle \mbox{2. }\quad \sum_{0\leq k \leq n/2}\, (-1)^k\, \binom{n\, -\, k}{k}\, 2^{n-2k}\, =\, n\, +\, 1\quad ?$

$\displaystyle \mbox{3. }\quad \sum_{k=0}^{n}\, \binom{n\, +\, k}{2k}\, 2^{n-k}\, =\, \dfrac{2^{2n+1}\, +\, 1}{3}\quad ?$

$\displaystyle \mbox{4. }\quad \sum_{k=0}^n\, \binom{2k}{k}\, \binom{n}{k}\, \left(-\dfrac{1}{4}\right)^k\, =\, 2^{-2n}\, \binom{2n}{n}\quad ?$

$\displaystyle \mbox{5. }\quad \sum_k\, \binom{m}{k}\, \binom{n\, +\, k}{m}\, =\, \sum_k\, \binom{m}{k}\, \binom{n}{k}\, 2^k\quad ?$

. . . . .$\mbox{Here }\, \binom{n}{k}\, = 0\, \mbox{ if }\, k\, >\, n.$
We'll be glad to help, but first we'll need to know where you're having trouble. What methods are you expected to use? What have you tried? How far have you gotten?

Please be complete. Thank you!

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•