16
$\begingroup$

I stumbled on the following identity, which has been checked numerically.

Question. Is this true? If so, any proof? $$\sum_{j=0}^{\lfloor\frac{k}2\rfloor}\binom{n-2k+j}{j,k-2j,n-3k+2j} =\sum_{j=0}^{\lfloor\frac{k}2\rfloor}\binom{n-k-2j-1}{k-2j}.$$

Here, $\binom{m}{a,b,c}$ is understood as $\frac{m!}{a!\,b!\,c!}$.

$\endgroup$
4
  • 1
    $\begingroup$ Set $m=n-2k$. Then $$ \binom{n-2k+j}{j,k-2j,n-3k+2j} = \binom{k-j}{j}\binom{m+j}{k-j} $$ and we sum over all values of $j$ (i.e., $0 \leq j \leq \lfloor k/2 \rfloor$ is the same as $0 \leq j \leq k-j$). $\endgroup$ Commented Jun 2, 2017 at 21:33
  • 1
    $\begingroup$ Good idea. Perhaps the summand on the RHS becomes $\binom{m+k-2j-1}{k-2j}$. Then what? $\endgroup$ Commented Jun 2, 2017 at 21:42
  • 1
    $\begingroup$ $\binom{m+k-2j-1}{k-2j} = \dim S^{k-2j} \mathbb{C}^m$ so RHS = dimension of forms in $m$ variables, of degree $\leq k$, of degree same parity as $k$... no idea if that helps. $\endgroup$ Commented Jun 2, 2017 at 21:49
  • $\begingroup$ I like the approach, Let's hope someone can pick up where you left off. $\endgroup$ Commented Jun 2, 2017 at 21:50

2 Answers 2

13
$\begingroup$

For convenience set $m=n-2k$. Then \begin{equation} \begin{split} \binom{n-2k+j}{j,k-2j,n-3k+2j} &= \binom{m+j}{j,k-2j,m-k+2j} \\ &= \binom{m+j}{m} \binom{m}{k-2j} \\ &= [t^j](1-t)^{-(m+1)} \cdot [t^{k-2j}](1+t)^m \\ &= [t^{2j}](1-t^2)^{-(m+1)} \cdot [t^{k-2j}](1+t)^m \end{split} \end{equation} where $[t^a]p$ is the coefficient of $t^a$ in the formal power series $p=p(t)$. Note that $[t^{2j+1}](1-t^2)^{-(m+1)} = 0$. So the left hand side is \begin{equation} \begin{split} [t^k](1-t^2)^{-(m+1)}(1+t)^m &= [t^k](1-t)^{-(m+1)}(1+t)^{-1} \\ &= \sum_{j=0}^k [t^{k-j}](1-t)^{-(m+1)} \cdot [t^j](1+t)^{-1} \\ &= \sum_{j=0}^k \binom{m+k-j}{m} (-1)^j \\ &= \sum_{j=0}^{\lfloor k/2 \rfloor} \binom{m+k-2j}{m} (-1)^{2j} + \binom{m+k-2j-1}{m} (-1)^{2j+1} \\ &= \sum_{j=0}^{\lfloor k/2 \rfloor} \binom{m+k-2j}{m}-\binom{m+k-2j-1}{m} \\ &= \sum_{j=0}^{\lfloor k/2 \rfloor} \binom{m+k-2j-1}{m-1} \end{split} \end{equation} as desired.

$\endgroup$
1
  • 1
    $\begingroup$ Great! It is a cool proof, in the true fashion of generatingfunctionology. $\endgroup$ Commented Jun 3, 2017 at 3:33
9
$\begingroup$

As functions of $k$, it appears that both sides satisfy the recurrence \begin{align} & 4(-n+2\,k+1) (-n+2k) A(n,k) \\[6pt] & {} + (8k^2-8\,kn+n^2+10k-9n) A(n,k+1)\\[6pt] & {} + (k+2)(-n+k) A(n,k+2)=0 \end{align} with $A(n,0) = 1$, $A(n,1) = n-2$.

$\endgroup$
3
  • $\begingroup$ Interesting. Can this be justified? $\endgroup$ Commented Jun 2, 2017 at 18:12
  • $\begingroup$ @T.Amdeberhan It looks like this might be gotten from a suitable extension of Gosper's algorithm / WZ pairs? $\endgroup$ Commented Jun 2, 2017 at 22:30
  • $\begingroup$ Not in a transparent way, really. $\endgroup$ Commented Jun 3, 2017 at 3:34

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.