2
$\begingroup$

Does anyone know a strategy for proving $$ 2\cdot(2k-3)!!=\sum_{i=1}^{k-1}(2i-3)!!(2(k-i)-3)!!\binom{k}{i} $$ for $k\geq 2$? Note that $(-1)!!=1$. Hints would be most appreciated. Full solutions not so much.

I have considered induction but whereas the left hand side is multiplied by the next odd number in the induction step the right hand side becomes one term longer and each term is multiplied by a different factor.

$\endgroup$

1 Answer 1

4
$\begingroup$

First note that $$(2n-1)!!=\frac{(2n)!}{2^nn!}\;,$$ so that the desired identity can be written

$$\begin{align*} \frac{2(2k-2)!}{2^{k-1}(k-1)!}&=\sum_{i=1}^{k-1}\left(\frac{(2i-2)!}{2^{i-1}(i-1)!}\cdot\frac{\big(2(k-i)-2\big)!}{2^{k-i-1}(k-i-1)!}\binom{k}i\right)\\\\ &=\frac1{2^{k-2}}\sum_{i=1}^{k-1}\frac{(2i-2)!(2k-2i-2)!k!}{i!(i-1)!(k-i)!(k-i-1)!}\\\\ &=\frac{k!}{2^{k-2}}\sum_{i=1}^{k-1}\left(\frac1i\binom{2(i-1)}{i-1}\cdot\frac1{k-i}\binom{2(k-i-1)}{k-i-1}\right)\\\\ &=\frac{k!}{2^{k-2}}\sum_{i=1}^{k-1}C_{i-1}C_{(k-2)-(i-1)}\\\\ &=\frac{k!}{2^{k-2}}\sum_{i=0}^{k-2}C_iC_{(k-2)-i} \end{align*}$$

where $C_n$ is the $n$-th Catalan number. Now do a little simplification and apply a basic Catalan identity, and you’ll have it.

$\endgroup$
4
  • $\begingroup$ @String: You’re welcome! (Someone really went out of his way to disguise what was going on in that identity!) $\endgroup$ Commented Oct 19, 2013 at 19:13
  • $\begingroup$ @Brian: I know it's been a while, but I was wondering if you could explain why the first equality of the second equation holds? $\endgroup$
    – nokiddn
    Commented Oct 2, 2014 at 7:57
  • 2
    $\begingroup$ @nokiddn: Identity is not known to hold at that point in Brian's derivation. It is just rewriting my original desired identity by substituting the known identity $$(2n-1)!!=\frac{(2n)!}{2^n n!}$$ for the cases $2n-1=2k-3,2n-1=2i-3$ and $2n-1=2(k-i)-3$ that appeared in my original desired identity, if that makes sense :) $\endgroup$
    – String
    Commented Oct 2, 2014 at 11:48
  • $\begingroup$ @String: I get it now, many thanks :) $\endgroup$
    – nokiddn
    Commented Oct 9, 2014 at 13:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .