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

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.
