Double factorial identity

922 Views Asked by At

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.

1

There are 1 best solutions below

4
On BEST ANSWER

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.