Some time ago, as a by-product of a proof, I came across an odd (at least to me) identity for reducing the factorial of an even number into a sum:
$$(2n)!=\sum_{k=0}^{\lfloor \frac{n}2 \rfloor} \frac{2^{n-2k} (n!)^3}{(n-2k)!\,(k!)^2}$$
I was wondering how one might go about to prove this directly (not as the by-product of my proof), and thought this might be an interesting challenge to play around with. For example, it doesn't seem very suited for induction, as the additional factors incurred from $n\to n+1$ are different for each summand.
Three remarks:
- I tried to search for this identity without success, and would be interested in a reference if someone has seen similar things show up somewhere else.
- Edit: I've successfully checked this identity with a Maple script up to $n=1000$, which makes me quite certain that I've not made a mistake in the proof (the indirect version mentioned above).
- If this challenge turns out to be too easy, I have a more complicated variant to offer. Edit2: After Semiclassical solved the question, I have posted the other one here.
First, by dividing both sides by $(n!)^2$ and organizing the factorials into binomial coefficients we obtain the suggestive form
$$\binom{2n}{n}\overset{?}{=}\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{k}\binom{n-k}{k}2^{n-2k}$$ We verify this expression by a double counting argument. Consider a $2\times n$ array consisting of equal numbers of zeros and ones.
Method $1$: Each array has $2n$ entries and $n$ ones to place within, so there are $\boxed{\binom{2n}{n}}$ arrays.
Method $2$: We may generate such an array selecting $k$ of the $n$ columns to receive no zeros, $l$ of the remaining $n-k$ columns to receive two ones, and then all of the $n-k-l$ columns left to receive a single one; the first step can be done in $\binom{n}{k}$ ways, the second in $\binom{n-k}{l}$ ways, and the last in $2^{n-k-l}$ ways since each column has two entries. Since we should assign exactly $n$ ones, we have the constraint $2l+(n-k-l)=n\implies l=k$. Since we must have $k\geq 0$ and $n-2k\geq 0$, summing over all possible $k$ yields the total number of such arrays as $\boxed{\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{k}\!\!\binom{n-k}{k}2^{n-2k}}.$
Since the two methods count the same objects, the boxed expressions are equal and the desired identity is valid.