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
    Commented Nov 26, 2019 at 14:52
  • $\begingroup$ @Gabe yes, it's a floor function $\endgroup$
    – Chen Chen
    Commented Nov 26, 2019 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
    Commented Nov 26, 2019 at 14:57
  • $\begingroup$ @Gabe sorry I had a typo, I corrected the orignal question. apologies ... $\endgroup$
    – Chen Chen
    Commented Nov 26, 2019 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
    Commented Nov 26, 2019 at 16:28

1 Answer 1

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
    Commented Nov 26, 2019 at 16:39
  • $\begingroup$ Wikipedia on formal power series has additional information. $\endgroup$ Commented Nov 26, 2019 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
    Commented Nov 26, 2019 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$ Commented Nov 26, 2019 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
    Commented Nov 26, 2019 at 19:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .