7
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ Are the brackets supposed to be a floor function? $\endgroup$
    – Gabe
    Nov 26 '19 at 14:52
  • $\begingroup$ @Gabe yes, it's a floor function $\endgroup$
    – Chen Chen
    Nov 26 '19 at 14:53
  • 1
    $\begingroup$ Plugging in n=3 the LHS evaluates to 3 + 18 + 12 + 8 = 41 and the RHS evaluates to 35 I think. $\endgroup$
    – Gabe
    Nov 26 '19 at 14:57
  • $\begingroup$ @Gabe sorry I had a typo, I corrected the orignal question. apologies ... $\endgroup$
    – Chen Chen
    Nov 26 '19 at 14:58
  • 1
    $\begingroup$ 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$. $\endgroup$
    – rogerl
    Nov 26 '19 at 16:28
2
$\begingroup$

We start with

$$\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}.}$$

$\endgroup$
6
  • $\begingroup$ Can you elaborate the step when you introduce $z$? wasn't familiar with that $\endgroup$
    – Chen Chen
    Nov 26 '19 at 16:39
  • $\begingroup$ Wikipedia on formal power series has additional information. $\endgroup$ Nov 26 '19 at 16:41
  • $\begingroup$ 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}.$$ $\endgroup$
    – Chen Chen
    Nov 26 '19 at 17:45
  • $\begingroup$ 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}.$ $\endgroup$ Nov 26 '19 at 17:49
  • $\begingroup$ 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}$? $\endgroup$
    – Chen Chen
    Nov 26 '19 at 19:55

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.