I recently noted that $$\sum_{k=0}^{n/2} \left(\frac{1}{3}\right)^k\binom{n+k}{k}\binom{2n+1k}{n+1+k}=3^n$$ Is this a known binomial identity? Any proof or reference?
Mathematica immediately returns $3^n$ when asked
Sum[(1/3)^k Binomial[n + k, k] Binomial[2 n + 1  k, n + 1 + k], {k,0, n/2}]
so there is most likely easy to prove it automatically using some Zeilberger magic.
The alternating signs suggests a combinatorial proof using the inclusion/exclusion principle.
Addendum: Standard rewriting techniques (and put $n=2n$), gives the equivalent form $$\sum_{k=0}^n (1)^{nk} 3^k \binom{3nk}{2n}\binom{3n+1+k}{2k} = 27^n$$ which IMHO, looks easier to prove with a bijective argument.

$\begingroup$ I checked the sum by using Maple, but I wonder if there is a "human" proof. $\endgroup$ – user45868 Jan 22 '14 at 18:54

1$\begingroup$ see e.g. the book "A=B": math.upenn.edu/~wilf/AeqB.html $\endgroup$ – Dima Pasechnik Jan 22 '14 at 20:39
I rewrote your identity in an equivalent form $$ \sum_{k=0}^{n/2} (1)^k 3^{nk} \binom{n+k}{n, k} \binom{2nk+1}{n2k, n+k+1} = 3^{2n} , $$ and attempted to construct a proof by induction on $n$. I did not succeed, but discovered an interesting hurdle: to prove the equally curious identity $$ \sum_{k=0}^{n/2} (1)^k 3^{nk} \binom{n+k}{n, k} \binom{2nk2}{n2k, n+k2} = 0 . $$
Does this latter identity have a human proof? Here's a sketch of how I obtained the latter identity by rewriting the original equation.
By Pascal's rule we have $ \binom{n+k}{n, k} = \binom{n+k1}{n1, k} + \binom{n+k1}{n, k1}; $ similarly $ \binom{2nk+1}{n2k, n+k+1} = 3 \binom{2nk1}{n2k1, n+k} + \binom{2nk2}{n2k3, n+k+1} + \binom{2nk 2}{n2k, n+k2} . $ Multiply these and regroup: the original summation now equals $$ \sum_{k=0}^{n/2} (1)^k 3^{nk} \binom{n+k1}{n1, k} \ 3 \binom{2nk1}{n2k1, n+k} $$ $$ + \sum_{k=0}^{n/2} (1)^k 3^{nk} \binom{n+k1}{n, k1} \ 3 \binom{2nk1}{n2k1, n+k} + \sum_{k=0}^{n/2} (1)^k 3^{nk} \binom{n+k}{n, k} \binom{2nk2}{n2k3, n+k+1} $$ $$ + \sum_{k=0}^{n/2} (1)^k 3^{nk} \binom{n+k}{n, k} \binom{2nk2}{n2k, n+k2} . $$
Evaluate this first summation by the induction hypothesis and obtain $9 \cdot 3^{2(n1)}$, which equals $3^{2n}$ as desired. The second and third summations are identical to each other except for a change of sign; together their sum is 0. So our proof by induction (of the original statement) would conclude if we establish that this fourth summation equals 0.
This is a response to Joe Alfano's comment. Define the two discrete functions $$F(n,k):=(1)^k3^{nk}\binom{n+k}k\binom{2nk2}{n2k} \qquad \text{and} \qquad G(n,k):=(1)^{k1}3^{n+1k}\binom{n+k1}{k1}\binom{2nk1}{n2k}.$$ The proof for the identity $\sum_{k\geq0}F(n,k)=0$ follows from $$F(n,k)=G(n,k+1)G(n,k).\tag1$$ Equation (1) can be verified say up on dividing through by $F(n,k)$ and simplifying. The rest comes from summing (1) over all integers $k$ and where the convention $\binom{a}b=0$ (if $b>a$ or $b<0$) is brought to bear. In this regard, the RHS of (1) telescopes $\sum_kG(n,k+1)\sum_kG(n,k)=0$. Hence $\sum_{k\in\mathbb{Z}}F(n,k)=\sum_{k=0}^{\lfloor\frac{n}2\rfloor}F(n,k)=0$, as desired.
=================
Now, back to the original problem from the OP. Define the functions $$A(n,k):=\frac{(1)^k}{3^{n+k}}\binom{n+k}k\binom{2n+1k}{n2k}, \qquad \text{and} \qquad B(n,k):=\frac{(1)^{k1}}{3^{n+k}}\binom{n+k}{k1}\binom{2n+2k}{n+12k}.$$ Again, one checks $A(n+1,k)A(n,k)=B(n,k+1)B(n,k)$ and then sum over the integers $k$. The outcome is $\sum_kA(n+1,k)\sum_kA(n,k)=0$. That is to say, the sum $\sum_kF(n,k)=\sum_{k=0}^{n/2}\frac{(1)^k}{3^{n+k}}\binom{n+k}k\binom{2n+1k}{n2k}$ is identically a constant. A quick check at $n=0$ reveal that the constant is $1$. The proof ends here.