How prove binomial cofficients $\sum_{k=0}^{[\frac{n}{3}]}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=[\frac{n}{2}]}^n\binom{n+1}{k}\binom{k}{n-k}$ How prove this  $$\sum_{k=0}^{[\frac{n}{3}]}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=[\frac{n}{2}]}^n\binom{n+1}{k}\binom{k}{n-k}$$
This equation How prove it? Thank you
I want take this  $$f(x)=(1-x)^{n+1}?$$
But I can't deal this $[n/3]$,
Thank you for you help
 A: Start from the RHS. We are counting the number of ways to choice $k$ elements among $n+1$, then choice $n-k$ elements among the $k$ elements previously chosen. If we imagine to assign a $+1$ weight in the first step, then increase the weight in the second step, we are counting the number of ways to assign a $+1$ or $+2$ weigth to the elements of a subset of $\{1,\ldots,n+1\}$ in such a way that the sum of the weights is just $n$. Rephrasing in the analytic combinatorics framework:
$$RHS=\sum_{k=\lfloor n/2\rfloor}^{n}\binom{n+1}{k}\binom{k}{n-k}=[x^n]\,\left((1+x+x^2)^{n+1}\right).\tag{1}$$
Now $1+x+x^2  =(1+x)^2-x$, so, for istance:
$$[x^n](1+x+x^2)^{n+1} = [x^n]\sum_{j=0}^{n+1}\binom{n+1}{j}(-1)^j x^j(x+1)^{2n+2-2j}=\sum_{j=0}^{n+1}(-1)^j\binom{n+1}{j}\binom{2n+2-2j}{n-j},$$
just like $1+x+x^2=\frac{1-x^3}{1-x}$ and
$$\frac{1}{(1-x)^m}=\sum_{j=0}^{+\infty}\binom{m+j-1}{j}x^j,$$
give:
$$[x^n](1+x+x^2)^{n+1}=[x^n]\left(\sum_{j=0}^{n+1}\binom{n+1}{j}(-1)^j x^{3j}\right)\cdot\left(\sum_{j=0}^{+\infty}\binom{n+j}{j}x^j\right).\tag{2}$$
Regarding $(2)$ as a Cauchy product gives $RHS=LHS$, QED.
The saddle-point method gives also:
$$[x^n](1+x+x^2)^{n+1}=\frac{3^{n+2}}{\sqrt{\pi(12n+30)}}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right).$$
A: By  way of  enrichment here  is  another algebraic  proof using  basic
complex variables, quite similar to the accepted answer.

Note that  the second binomial  coefficient in both sums  controls the
range of the sum, so we can write our claim like this:
$$\sum_{k=0}^{n+1} {n+1\choose k} (-1)^k {2n-3k\choose n-3k}
= \sum_{k=0}^{n+1} {n+1\choose k} {k\choose n-k}.$$
To evaluate the LHS introduce the integral representation 
$${2n-3k\choose n-3k} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{2n-3k}}{z^{n-3k+1}} \; dz.$$
We can check that this really is zero when $k>\lfloor n/3\rfloor.$
This gives for the sum the representation
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{2n}}{z^{n+1}} 
\sum_{k=0}^{n+1} {n+1\choose k} 
(-1)^k \left(\frac{z^3}{(1+z)^3}\right)^k
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{2n}}{z^{n+1}} 
\left(1-\frac{z^3}{(1+z)^3}\right)^{n+1} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n+1}} \frac{1}{(1+z)^{n+3}}
\left(3z^2+3z+1\right)^{n+1} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n+1}} \frac{1}{(1+z)^{n+3}}
\sum_{q=0}^{n+1} {n+1\choose q} 3^q z^q (1+z)^q \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\sum_{q=0}^{n+1} {n+1\choose q} 3^q z^{q-n-1} (1+z)^{q-n-3} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\sum_{q=0}^{n+1} {n+1\choose q} 3^q 
\frac{1}{z^{n+1-q}} \frac{1}{(1+z)^{n+3-q}} \; dz.$$
Computing the residue we find
$$\sum_{q=0}^{n+1} {n+1\choose q} 3^q (-1)^{n-q}
{n-q+n+2-q\choose n+2-q}
= \sum_{q=0}^{n+1} {n+1\choose q} 3^q (-1)^{n-q}
{2n-2q+2\choose n-q+2}.$$
Now introduce the integral representation
$${2n-2q+2\choose n-q+2}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{2n-2q+2}}{z^{n-q+3}} \; dz$$
which gives for the sum the integral
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{2n+2}}{z^{n+3}} 
\sum_{q=0}^{n+1} {n+1\choose q} 3^q (-1)^{n-q}
\left(\frac{z}{(1+z)^2}\right)^q
\; dz
\\ = - \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{2n+2}}{z^{n+3}} 
\left(\frac{3z}{(1+z)^2}-1\right)^{n+1}
\; dz
\\ = - \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n+3}} (-1+z-z^2)^{n+1}
\; dz.$$
Put $w=-z$ which just rotates the small circle to get
$$\frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{1}{(-w)^{n+3}} (-1-w-w^2)^{n+1}
\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\epsilon}
\frac{1}{w^{n+3}} (1+w+w^2)^{n+1} \; dw.$$
We get for the final answer
$$[w^{n+2}] (1+w+w^2)^{n+1}$$
but we have $2n+2-n-2 = n$ and thus exploiting the symmetry
of $1+w+w^2$ we get
$$[w^n] (1+w+w^2)^{n+1}.$$
To evaluate the RHS introduce the integral representation 
$${k\choose n-k} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^k}{z^{n-k+1}} \; dz.$$
This gives for the sum the representation
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n+1}}
\sum_{k=0}^{n+1} {n+1\choose k} \left((1+z)z\right)^k \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n+1}} (1+z(1+z))^{n+1} \; dz
.$$
The answer is
$$[z^n] (1+z+z^2)^{n+1},$$
the same as the LHS, and we are done.

We have  not made use of  the properties of complex  integrals here so
this  computation  can  also   be  presented  using  just  algebra  of
generating functions.

This MSE link has another computation in the same spirit.

Apparently  this method is  due to  Egorychev although  some of  it is
probably folklore.
