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

Question

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

So I feel like $(-1)^k$ is almost designed for the inclusion-exclusion principle. And the left-hand side looks like some sort of pairing, so I am interested in some combinatorics proof like below-linked question. But using a generating function is always helpful.

[EDIT] now I am probably equally, if not more interested in a generating function solution now that I see below answer that completely makes sense to me, but with some issues in signs..

Evaluation of a sum of $(-1)^{k} {n \choose k} {2n-2k \choose n+1}$

Answer 1

We seek to show that

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

The LHS is

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

Now the coefficient extractor $[z^{n-1}]$ combined with the $z^{2k}$ term enforces the range, making for a zero contribution when $2k\gt n-1$ and we may continue with

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

This is

$$\sum_{q=0}^{n-1} (-1)^q {q+2\choose q} {n+1\choose n-1-q} 2^{n-1-q}.$$

Observe that

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

This yields for the sum

$${n+1\choose 2} \sum_{q=0}^{n-1} (-1)^q {n-1\choose q} 2^{n-1-q} \\ = {n+1\choose 2} (-1+2)^{n-1} = {n+1\choose 2}.$$

We have the claim.

Answer 2

Coefficient of $x^k$ in $(1-x)^{n+1}$ is $(-1)^k$${n+1 \choose k}$

---

Coefficient of $$x^{(\frac{n-2k-1}{2})}$$ in $$(1- \sqrt{x})^{-(n+1)}$$ is ${{2n-2k-1} \choose n}$

---

In all what we want is coefficient of (multiplying previous 2 series)$$x^{(\frac{n-1}{2})}$$ in $$(1 +\sqrt{x})^{n+1}$$ which is nothing but ${{n+1} \choose 2}$

---

Answer 3

Both sides of the equation are the answer to the following question:

How many sequences of $n$ zeroes and $n-1$ ones are there where no two ones are adjacent?

To see why $n(n+1)/2$ answers this question, note that the $n-1$ ones divide each valid sequence into $n$ sections; a section before the first one (possible empty), a section after the last one (possibly empty), and $n-2$ sections between each adjacent pair. Each of the middle $n-2$ sections must have at least one zero. After placing these $n-2$ zeroes, there are two remaining zeroes to place. The number of ways to place two identical objects into $n$ sections is $\binom{n}2+n=n(n+1)/2$, by conditioning on whether the zeroes are placed into the same section.

Now, we need to explain why number of such sequences is also counted by the left hand side of the equation. Instead of using the ones to divide each sequence into $n$ sections, we use the zeroes to divide each sequence into $n+1$ sections. For each $1\le i\le n+1$, let $A_i$ be the set of sequences where the $i^{th}$ section contains two or more ones. We want to count $$ |A_1^c\cap A_2^c\cap \dots \cap A_{n+1}^c| $$ which by the principle of inclusion exclusion is $$ \binom{2n-1}{n}-\sum_{k=1}(-1)^{k+1}\sum_{1\le i_1<i_2<\dots<i_k\le n+1}|A_{i_1}\cap A_{i_2}\cap \dots \cap A_{i_k}| $$ Each intersection $A_{i_1}\cap A_{i_2}\cap \dots \cap A_{i_k}$ is easy to count; first, choose an arbitrary sequence of $n$ zeroes and $n-2k-1$ ones, then add an extra two ones two each of sections $i_1,i_2,\dots,i_k$. This shows the number of such sequences in this intersection is $\binom{2n-1-2k}n$. Since there are $\binom{n+1}k$ intersections which contribute this sum, the above exactly simplifies to the LHS of the equation we want to prove.