Semifactorial Identity

Question

I was wondering if anyone had any insight on how to prove the following identity:

For all $m \in \mathbb{N}$ $$ \frac{1}{2m-1} + \frac{2m-2}{(2m-1)(2m-3)} + \frac{(2m-2)(2m-4)}{(2m-1)(2m-3)(2m-5)} + \cdots + \frac{(2m-2)!!}{(2m-1)!!} = 1$$

I attempted to rewrite and simplify the left hand side as: $$ \sum_{k = 1}^m \frac{\frac{(2m-2)!!}{(2m-2k)!!}}{\frac{(2m-1)!!}{(2m-2k-1)!!}} = \sum_{k = 1}^m \frac{(2m-2)!! (2m-2k-1)!!}{(2m-2k)!! (2m-1)!!} = \frac{\left[2^{m-1} (m-1)! \right]^2}{(2m-1)!} \sum_{k=1}^m \frac{(2m-2k-1)!!}{(2m-2k)!!} $$

But I do not seem to be getting anywhere. Does anyone see how to prove the statement?

Answer 1

I believe this can be proven combinatorially by recasting it as $$(2m-3)!! + (2m-2)(2m-5)!! + (2m-2)(2m-4)(2m-7)!! + \cdots + (2m-2)!! = (2m-1)!!$$

To do this, we note that $(2m-1)!!$ counts the number of perfect matchings of the complete graph $K_{2m}$. Label the vertices of $K_{2m}$ with the integers $1 \ldots 2m$, and consider any perfect matching of $K_{2m}$. Let $n$ be the integer such that $\{1,n\}$ is an edge of the matching, and color blue any edge of the matching which contains a vertex labelled less than $n$. Every perfect matching can be colored uniquely in this way, therefore the perfect matchings of $K_{2m}$ are the disjoint union of those matchings with $k$ blue edges, as $k$ varies from 1 to $m$ (note that the edge $\{1,n\}$ is always colored blue).

Let's count the number of matchings with $k$ blue edges. If $k=1$, then the blue edge must be $\{1,2\}$ since if $\{1,2\}$ is not an edge of the matching, both edges containing 1 and 2 would be blue. The remainder of the matching can be chosen in $(2m-3)!!$ ways, yielding $(2m-3)!!$ perfect matchings with one blue edge.

If $k=2$, then $\{1,2\}$ is not an edge of the matching, so the edge of the matching containing 2 must be colored blue. This edge can be picked in $2m-2$ ways, since the other vertex of the edge may be any other than 1 or 2. Since $k=2$, there can be only one more blue edge, which necessarily is an edge containing the vertex 1. This will be either $\{1,4\}$, if $\{2,3\}$ is the other blue edge, or $\{1,3\}$ otherwise. The remainder of the match can be chosen in $(2m-5)!!$ ways, yielding $(2m-2)(2m-5)!!$ perfect matchings with 2 blue edges.

For general $k$, we proceed as above. For each $i \in \{1\ldots k-1\}$, we create a blue edge by picking the smallest unmatched vertex greater than 1, and finding it a mate distinct from 1 that has not yet been matched; at each step, this can be done in $2m-2i$ ways ($2i-2$ already matched vertices, 1, and the vertex in question are excluded). After this process is complete, the $k^{th}$ edge must be created by connecting the vertex 1 to the remaining unmatched vertex with the smallest label, for which there is only one choice. The remainder of the perfect match can be made in $(2(m-k)-1)!!$ ways.

Adding up all of these counts as $k$ varies from 1 to $m$ yields the left-hand side of the identity above.

Answer 2

Starting from

$$\sum_{k=1}^m \frac{(2m-2)!!/(2m-2k)!!}{(2m-1)!!/(2m-2k-1)!!}$$

and using

$$(2n)!! = 2^n n! \quad\text{and}\quad (2n-1)!! = \frac{(2n)!}{2^n n!}$$

we get for the sum

$$\sum_{k=1}^m \frac{2^{m-1} (m-1)!}{2^{m-k} (m-k)!} \frac{(2m-2k)! / 2^{m-k} / (m-k)!}{(2m)! / 2^{m} / m!} \\ = \frac{(m-1)! m!}{(2m)!} \sum_{k=1}^m {2m-2k\choose m-k} 2^{2k-1} \\ = - \frac{(m-1)! m!}{(2m)!} {2m\choose m} \frac{1}{2} + \frac{(m-1)! m!}{(2m)!} \sum_{k=0}^m {2m-2k\choose m-k} 2^{2k-1} \\ = -\frac{1}{2m} + \frac{(m-1)! m!}{(2m)!} \sum_{k=0}^m {2m-2k\choose m-k} 2^{2k-1} \\ = -\frac{1}{2m} + \frac{1}{2m} {2m\choose m}^{-1} \sum_{k=0}^m {2m-2k\choose m-k} 2^{2k}.$$

Continuing with the sum term yields

$$\sum_{k=0}^m [z^{m-k}] (1+z)^{2m-2k} 2^{2k} = [z^m] (1+z)^{2m} \sum_{k=0}^m z^k (1+z)^{-2k} 2^{2k}.$$

We may extend $k$ to infinity because when $k\gt m$ there is no contribution to $[z^m]$. We obtain for the coefficient extractor

$$[z^m] (1+z)^{2m} \sum_{k\ge 0} z^k (1+z)^{-2k} 2^{2k} = [z^m] (1+z)^{2m} \frac{1}{1-4z/(1+z)^2} \\ = [z^m] (1+z)^{2m+2} \frac{1}{(1-z)^2}.$$

This is

$$\sum_{q=0}^m {2m+2\choose q} (m+1-q) = (m+1) \sum_{q=0}^m {2m+2\choose q} - \sum_{q=0}^m {2m+2\choose q} q.$$

The first piece yields

$$(m+1) \frac{1}{2} \left(2^{2m+2} - {2m+2\choose m+1} \right)$$

and the second

$$\sum_{q=1}^m {2m+2\choose q} q = (2m+2) \sum_{q=1}^m {2m+1\choose q-1} = (2m+2) \sum_{q=0}^{m-1} {2m+1\choose q} \\ = (2m+2)\frac{1}{2} \left(2^{2m+1} - 2 {2m+1\choose m}\right).$$

Subtract to obtain

$$(2m+2) {2m+1\choose m} - \frac{1}{2} (m+1) {2m+2\choose m+1} \\ = (2m+2) {2m+1\choose m} - \frac{1}{2} (m+1) \frac{2m+2}{m+1} {2m+1\choose m} \\ = (m+1) {2m+1\choose m} = (m+1) \frac{2m+1}{m+1} {2m\choose m} = (2m+1) {2m\choose m}.$$

Returning to the main computation we thus have

$$-\frac{1}{2m} + \frac{1}{2m} (2m+1) = 1$$

as desired.

Answer 3

$$\scriptsize\begin{align} &\;\;\;\frac 1{2m-1}+\frac {2m-2}{(2m-1)(2m-3)}+\frac{(2m-2)(2m-4)}{(2m-1)(2m-3)(2m-5)}+\cdots+\frac {(2m-2)!!}{(2m-1)!!}\\\\ &=\frac 1{2m-1}\left(1+\frac {2m-2}{2m-3}\left(1+\frac {2m-4}{2m-5}\left(1+\;\;\cdots\;\;\ \left(1+\frac 65\left(1+\frac 43\left(1+\frac 21\right)\right)\right)\right)\cdots+\right)\right)\\\\ &=\frac 1{2m-1}\left(1+\frac {2m-2}{2m-3}\left(1+\frac {2m-4}{2m-5}\left(1+\;\;\cdots\;\;\ \left(1+\frac 65\left(1+\frac 43\cdot \color{blue}3\right)\right)\right)\cdots+\right)\right)\\\\ &=\frac 1{2m-1}\left(1+\frac {2m-2}{2m-3}\left(1+\frac {2m-4}{2m-5}\left(1+\;\;\cdots\;\;\ \left(1+\frac 65\cdot \color{blue}5\right)\right)\cdots+\right)\right)\\\\ &\qquad\qquad \vdots\qquad\qquad\qquad\qquad\qquad \;\unicode{x22F0} \\\\ &=\frac 1{2m-1}\left(1+\frac {2m-2}{2m-3}\left(1+\frac {2m-4}{2m-5}\cdot \color{blue}{(2m-5)}\right)\right)\\\\ &=\frac 1{2m-1}\left(1+\frac {2m-2}{2m-3}\cdot \color{blue}{(2m-3)}\right)\\\\ &=\frac 1{2m-1}\cdot \color{blue}{(2m-1)}\\\\ &=\color{red}{\large 1}\\\\\end{align}$$

---

In alternative notation, starting from the innermost parenthesis,

$$\scriptsize\begin{align} a_1\;\;&=1+\frac 21&&=3\\ a_2\;\;&=1+\frac 43a_1&&=5\\ a_3\;\;&=1+\frac 65 a_2&&=7\\ &\qquad \vdots &\qquad \\ a_n\;\;&=1+\frac {2n}{2n-1}a_{n-1}&&=2n+1\\ &\qquad \vdots &\qquad \\ a_{m-1}&=1+\frac {2m-2}{2m-3}\cdot {(2m-3)}&&=2m-1\\ S\;\;\;&=\frac 1{2m-1}a_{m-1}&&=1 \end{align}$$