8
$\begingroup$

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?

$\endgroup$

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I checked the sum by using Maple, but I wonder if there is a "human" proof. $\endgroup$
    – user45868
    Jan 22, 2014 at 18:54
  • 1
    $\begingroup$ see e.g. the book "A=B": math.upenn.edu/~wilf/AeqB.html $\endgroup$ Jan 22, 2014 at 20:39
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.