# Prove that $\sum_{k=0}^{n} 2^{k} {n \choose k}{n-k \choose \lfloor{\frac{n-k}{2}}\rfloor} = {2n+1 \choose n}$

The problem is the following: prove that $$\sum_{k=0}^{n} 2^{k} {n \choose k}{n-k \choose \lfloor{\frac{n-k}{2}}\rfloor} = {2n+1 \choose n}$$

I was trying to prove some concrete combinatorial examples to make the LHS equivalent to $$2n+1 \choose n$$.

We choose $$k$$ in the first $$n$$ items, but I am not sure how to map $$2^{k} {n-k \choose \lfloor{\frac{n-k}{2}}\rfloor}$$ to choosing $$n-k$$ elements from $$n+1$$ items

[EDIT] This might help. Combinatorial proof $\sum_i^{\lfloor{n/2}\rfloor} (-1)^i {n-i\choose i} 2^{n-2i} = n+1$

• Are the brackets supposed to be a floor function?
– Gabe
Nov 26 '19 at 14:52
• @Gabe yes, it's a floor function Nov 26 '19 at 14:53
• Plugging in n=3 the LHS evaluates to 3 + 18 + 12 + 8 = 41 and the RHS evaluates to 35 I think.
– Gabe
Nov 26 '19 at 14:57
• @Gabe sorry I had a typo, I corrected the orignal question. apologies ... Nov 26 '19 at 14:58
• Note that $2^{k} {n-k \choose \lfloor{\frac{n-k}{2}}\rfloor}\ne \binom{n+1}{n-k}$ in general; for example set $n=4$, $k=2$. Nov 26 '19 at 16:28

$$\sum_{k=0}^n 2^k {n\choose k} {n-k\choose \lfloor \frac{n-k}{2} \rfloor} = \sum_{k=0}^n 2^{n-k} {n\choose k} {k\choose \lfloor k/2 \rfloor} \\ = \sum_{k=0}^{\lfloor n/2\rfloor} 2^{n-2k} {n\choose 2k} {2k\choose k} + \sum_{k=0}^{\lfloor (n-1)/2\rfloor} 2^{n-2k-1} {n\choose 2k+1} {2k+1\choose k}.$$

Now for the first sum we write

$${n\choose 2k} {2k\choose k} = \frac{n!}{(n-2k)! \times k! \times k!} = {n\choose k} {n-k\choose n-2k}.$$

We obtain

$$\sum_{k=0}^{\lfloor n/2\rfloor} 2^{n-2k} {n\choose k} {n-k\choose n-2k} \\ = \sum_{k=0}^{\lfloor n/2\rfloor} 2^{n-2k} {n\choose k} [z^{n-2k}] (1+z)^{n-k} \\ = [z^n] (1+z)^n \sum_{k=0}^{\lfloor n/2\rfloor} 2^{n-2k} {n\choose k} z^{2k} (1+z)^{-k}.$$

Now the coefficient extractor enforces the sum limits and we may continue with

$$2^n [z^n] (1+z)^n \sum_{k\ge 0} 2^{-2k} {n\choose k} z^{2k} (1+z)^{-k} \\ = 2^n [z^n] (1+z)^n \left(1+\frac{z^2}{4(1+z)}\right)^n \\ = \frac{1}{2^n} [z^n] (z+2)^{2n} = \frac{1}{2^n} {2n\choose n} 2^n = {2n\choose n}.$$

For the second sum we write

$${n\choose 2k+1} {2k+1\choose k} = \frac{n!}{(n-2k-1)! \times k! \times (k+1)!} = {n\choose k} {n-k\choose n-2k-1}.$$

We obtain

$$\sum_{k=0}^{\lfloor (n-1)/2\rfloor} 2^{n-2k-1} {n\choose k} {n-k\choose n-2k-1} \\ = \sum_{k=0}^{\lfloor (n-1)/2\rfloor} 2^{n-2k-1} {n\choose k} [z^{n-2k-1}] (1+z)^{n-k} \\ = [z^{n-1}] (1+z)^n \sum_{k=0}^{\lfloor (n-1)/2\rfloor} 2^{n-2k-1} {n\choose k} z^{2k} (1+z)^{-k}.$$

Once more the coefficient extractor enforces the sum limits and we may continue with

$$2^{n-1} [z^{n-1}] (1+z)^n \sum_{k\ge 0} 2^{-2k} {n\choose k} z^{2k} (1+z)^{-k} \\ = 2^{n-1} [z^{n-1}] (1+z)^n \left(1+\frac{z^2}{4(1+z)}\right)^n \\ = \frac{1}{2^{n+1}} [z^{n-1}] (z+2)^{2n} = \frac{1}{2^{n+1}} {2n\choose n-1} 2^{n+1} = {2n\choose n-1}.$$

Collecting everything we find

$$\bbox[5px,border:2px solid #00A000]{ {2n\choose n} + {2n\choose n-1} = {2n+1\choose n}.}$$

• Can you elaborate the step when you introduce $z$? wasn't familiar with that Nov 26 '19 at 16:39
• Wikipedia on formal power series has additional information. Nov 26 '19 at 16:41
• Can you elaborate this step? I read about formal series but still not very sure how this step follows: $$2^{n-1} [z^{n-1}] (1+z)^n \sum_{k\ge 0} 2^{-2k} {n\choose k} z^{2k} (1+z)^{-k} \\ = 2^{n-1} [z^{n-1}] (1+z)^n \left(1+\frac{z^2}{4(1+z)}\right)^n \\ = \frac{1}{2^{n+1}} [z^{n-1}] (z+2)^{2n} = \frac{1}{2^{n+1}} {2n\choose n-1} 2^{n+1} = {2n\choose n-1}.$$ Nov 26 '19 at 17:45
• In going from (1) to (2) we use the binomial theorem. From (2) to (3) we first simplify the rational function that appears, then cancel the common term $(1+z)^n$ and collect powers of two. The third line is a routine coefficient extraction from the power $(z+2)^{2n}.$ Nov 26 '19 at 17:49
• Thanks, I think one last question -- forgive me if it;'s a basic question: how are you able to write ${n-k \choose n-2k} = z^{n-2k} (1+z)^{n-k}$? Nov 26 '19 at 19:55