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?