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?
[Math] Binomial Identity
co.combinatoricscombinatorial-identities
co.combinatoricscombinatorial-identities
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?
Best Answer
Mathematica immediately returns $3^n$ when asked
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.