Binomial Identity

Question

I recently noted that $$\sum_{k=0}^{n/2} \left(-\frac{1}{3}\right)^k\binom{n+k}{k}\binom{2n+1-k}{n+1+k}=3^n$$ Is this a known binomial identity? Any proof or reference?

Answer 1

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)^{n-k} 3^k \binom{3n-k}{2n}\binom{3n+1+k}{2k} = 27^n$$ which IMHO, looks easier to prove with a bijective argument.

Answer 2

I rewrote your identity in an equivalent form $$ \sum_{k=0}^{n/2} (-1)^k 3^{n-k} \binom{n+k}{n, k} \binom{2n-k+1}{n-2k, 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^{n-k} \binom{n+k}{n, k} \binom{2n-k-2}{n-2k, n+k-2} = 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+k-1}{n-1, k} + \binom{n+k-1}{n, k-1}; $ similarly $ \binom{2n-k+1}{n-2k, n+k+1} = 3 \binom{2n-k-1}{n-2k-1, n+k} + \binom{2n-k-2}{n-2k-3, n+k+1} + \binom{2n-k -2}{n-2k, n+k-2} . $ Multiply these and regroup: the original summation now equals $$ \sum_{k=0}^{n/2} (-1)^k 3^{n-k} \binom{n+k-1}{n-1, k} \ 3 \binom{2n-k-1}{n-2k-1, n+k} $$ $$ + \sum_{k=0}^{n/2} (-1)^k 3^{n-k} \binom{n+k-1}{n, k-1} \ 3 \binom{2n-k-1}{n-2k-1, n+k} + \sum_{k=0}^{n/2} (-1)^k 3^{n-k} \binom{n+k}{n, k} \binom{2n-k-2}{n-2k-3, n+k+1} $$ $$ + \sum_{k=0}^{n/2} (-1)^k 3^{n-k} \binom{n+k}{n, k} \binom{2n-k-2}{n-2k, n+k-2} . $$

Evaluate this first summation by the induction hypothesis and obtain $9 \cdot 3^{2(n-1)}$, 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.

Answer 3

This is a response to Joe Alfano's comment. Define the two discrete functions $$F(n,k):=(-1)^k3^{n-k}\binom{n+k}k\binom{2n-k-2}{n-2k} \qquad \text{and} \qquad G(n,k):=(-1)^{k-1}3^{n+1-k}\binom{n+k-1}{k-1}\binom{2n-k-1}{n-2k}.$$ 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+1-k}{n-2k}, \qquad \text{and} \qquad B(n,k):=\frac{(-1)^{k-1}}{3^{n+k}}\binom{n+k}{k-1}\binom{2n+2-k}{n+1-2k}.$$ 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+1-k}{n-2k}$ is identically a constant. A quick check at $n=0$ reveal that the constant is $1$. The proof ends here.