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$
  • 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$ – Zach Teitler Jun 2 '17 at 21:33
  • 1
    $\begingroup$ Good idea. Perhaps the summand on the RHS becomes $\binom{m+k-2j-1}{k-2j}$. Then what? $\endgroup$ – T. Amdeberhan Jun 2 '17 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$ – Zach Teitler Jun 2 '17 at 21:49
  • $\begingroup$ I like the approach, Let's hope someone can pick up where you left off. $\endgroup$ – T. Amdeberhan Jun 2 '17 at 21:50
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
    $\begingroup$ Great! It is a cool proof, in the true fashion of generatingfunctionology. $\endgroup$ – T. Amdeberhan Jun 3 '17 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$
  • $\begingroup$ Interesting. Can this be justified? $\endgroup$ – T. Amdeberhan Jun 2 '17 at 18:12
  • $\begingroup$ @T.Amdeberhan It looks like this might be gotten from a suitable extension of Gosper's algorithm / WZ pairs? $\endgroup$ – Steven Stadnicki Jun 2 '17 at 22:30
  • $\begingroup$ Not in a transparent way, really. $\endgroup$ – T. Amdeberhan Jun 3 '17 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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