Ytukyg

To find the sum:
$$sum_{k=0}^{n} (-1)^k binom{n}{k} binom{2n-k}{n}$$

Try:

I do not have any clue about the question. I was thinking of finding coefficient of some required power in a binomial expansion, but wasn't able to proceed as the power of $x$ seems to be non-constant in each term ($x^{n+k}$).

Please give a small hint!

$newcommand{bbx}[1]{,bbox[15px,border:1px groove navy]{displaystyle{#1}},}
newcommand{braces}[1]{leftlbrace,{#1},rightrbrace}
newcommand{bracks}[1]{leftlbrack,{#1},rightrbrack}
newcommand{dd}{mathrm{d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,mathrm{e}^{#1},}
newcommand{ic}{mathrm{i}}
newcommand{mc}[1]{mathcal{#1}}
newcommand{mrm}[1]{mathrm{#1}}
newcommand{pars}[1]{left(,{#1},right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{root}[2]{,sqrt[#1]{,{#2},},}
newcommand{totald}[3]{frac{mathrm{d}^{#1} #2}{mathrm{d} #3^{#1}}}
newcommand{verts}[1]{leftvert,{#1},rightvert}$
begin{align}
sum_{k = 0}^{n}pars{-1}^{k}{n choose k}{2n - k choose n} & =
sum_{k = 0}^{n}pars{-1}^{k}{n choose k}bracks{z^{n}}pars{1 + z}^{2n - k}
\[5mm] & =
bracks{z^{n}}pars{1 + z}^{2n}
sum_{k = 0}^{n}{n choose k}pars{-,{1 over 1 + z}}^{k}
\[5mm] & =
bracks{z^{n}}pars{1 + z}^{2n}pars{1 - {1 over 1 + z}}^{n} =
bracks{z^{n}}pars{1 + z}^{n},z^{n} = bbx{large 1}
end{align}

Note that
begin{align*}
sum_{k=0}^{n} (-1)^k binom{n}{k} binom{2n-k}{n}&=sum_{k=0}^{n} (-1)^k binom{n}{k} binom{2n-k}{n-k}\
&=sum_{k=0}^{n} (-1)^k binom{n}{k} (-1)^{n-k}binom{-(n+1)}{n-k}\
&=(-1)^{n}sum_{k=0}^{n} binom{n}{k} binom{-(n+1)}{n-k}\
&=(-1)^{n}binom{n-(n+1)}{n}=1.
end{align*}
where we used
$$binom{2n-k}{n-k}=frac{(2n-k)cdots(n+1)}{(n-k)!}=
(-1)^{n-k}frac{(-n-1)cdots(-2n+k)}{(n-k)!}=
(-1)^{n-k}binom{-n-1}{n-k}$$

and the Vandermonde's identity.

Another way is to exploit the Melzak's identity: $$fleft(x+yright)=xdbinom{x+n}{n}sum_{k=0}^{n}left(-1right)^{k}dbinom{n}{k}frac{fleft(y-kright)}{x+k},, x,yinmathbb{R},, xneq-k $$ where $f $ is an algebraic polynomial up to degree $n $. So taking $fleft(zright)=dbinom{z+n}{n}z$ we get $$sum_{k=0}^{n}left(-1right)^{k}dbinom{n}{k}dbinom{y+n-k}{n}frac{y-k}{-x-k}=-frac{dbinom{n+y+x}{n}}{xdbinom{x+n}{n}}left(x+yright)$$ so taking $y=n$ and the limit $xrightarrow-n$ we get $$sum_{k=0}^{n}left(-1right)^{k}dbinom{n}{k}dbinom{2n-k}{n}=-lim_{xrightarrow-n}frac{dbinom{2n+x}{n}}{xdbinom{x+n}{n}}left(n+xright)=color{red}{1}$$ as wanted.

I think that the simpler and shorter way would be:
$$
eqalign{
& sumlimits_{0, le ,k, le ,n} {left( { - 1} right)^{,k} left( matrix{
n cr
k cr} right)left( matrix{
2n - k cr
n cr} right)} = cr
& = sumlimits_{0, le ,k, le ,n} {left( matrix{
k - n - 1 cr
k cr} right)left( matrix{
2n - k cr
n cr} right)} = cr
& = sumlimits_{0, le ,k, le ,n} {left( matrix{
k - n - 1 cr
k cr} right)left( matrix{
2n - k cr
n - k cr} right)} = cr
& = left( matrix{
n cr
n cr} right) = 1 cr}
$$
where

• 1st step : Upper Negation $ left({ - 1} right)^{,k} left( matrix{
  n cr
  k cr}right)=left( matrix{
  {k-n-1} cr
  k cr}right)$


• 2nd step: Symmetry $left( matrix{
  n cr
  k cr}right)=left( matrix{
  n cr
  {n-k} cr}right)quad |0 le text{integer} ,n$


• 3rd step: Double Convolution
  $$
  sumlimits_{a, le ,k, le ,b} {left( matrix{
  k - c cr
  k - a cr} right)left( matrix{
  d - k cr
  b - k cr} right)} = left( matrix{
  d - c + 1 cr
  b - a cr} right)
  $$

There is also a combinatorial solution. Consider the following problem:

How many subsets of ${1,2,dots,2n}$ of size $n$ contain none of the numbers in ${1,2,dots,n}$?

On the one hand, the answer is obviously $1$; the only such subset is ${n+1,n+2,dots, 2n}$.

On the other hand, we can solve this with the principle of inclusion exclusion. Letting $E_i$ be the number of subsets of size $n$ which do contain $i$, we need to count $E_1^complementcap E_2^complementcap dots cap E_n^complement$. For any $k$ indices $i_1,dots,i_k$, the size of the intersection $E_{i_1}cap E_{i_2}cap dots cap E_{i_k}$ is $binom{2n-k}n$. Taking the alternating sum over all such subsets of indices, we get your sum.