# An equality between a product and a combinatorial sum

I'm trying to prove the following identity (of which I numerically verified the truth) :

$$\text{For every n\in\mathbb{N}^* and \alpha \in \mathbb{R}\setminus\lbrace-2k\text{ }|\text{ }k\in\mathbb{N}\rbrace,}$$

$$\text{\prod\limits_{k=1}^{n}}\left[1-\frac{1}{2k+\alpha}\right]=\frac{\alpha}{4^{n}}{2n \choose n}\text{\sum\limits_{k=0}^{n}}\frac{{n \choose k}^2}{{2n \choose 2k}}\frac{1}{2k+\alpha}$$

I've tried induction, unsuccessfully. Tbh, I don't really have any other ideas for tackling it. Products such as this are not that easy to work with.

Any ideas or suggestion ?

• Perhaps if you tell us how you came up with this, that might provide a lead? – joriki Sep 19 '18 at 19:21
• Well actually, I don't have more context either. It's some kind of "mathematical enigma" among many other proposed by a teacher at my uni, for enthousiastic students – Harmonic Sun Sep 19 '18 at 19:27

For the identity

$$\bbox[5px,border:2px solid #00A000]{ \prod_{k=1}^n \left[ 1 - \frac{1}{2k+\alpha} \right] = \frac{\alpha}{4^n} {2n\choose n} \sum_{k=0}^n {n\choose k}^2 {2n\choose 2k}^{-1} \frac{1}{2k+\alpha}}$$

we work with $$n\ge 2$$ and we first simplify the RHS

$$\frac{\alpha}{4^n} \frac{(2n)!}{n!\times n!} \sum_{k=0}^n \frac{n!^2}{k!^2 (n-k)!^2} \frac{(2k)! (2n-2k)!}{(2n)!} \frac{1}{2k+\alpha} \\ = \frac{\alpha}{4^n} \sum_{k=0}^n {2k\choose k} {2n-2k\choose n-k} \frac{1}{2k+\alpha} \\ = \frac{1}{4^n} {2n\choose n} + \frac{\alpha}{4^n} \sum_{k=1}^n {2k\choose k} {2n-2k\choose n-k} \frac{1}{2k+\alpha} .$$

Now for the LHS we find

$$\prod_{k=1}^n \frac{2k-1+\alpha}{2k+\alpha} = \prod_{k=1}^n (2k-1+\alpha) \prod_{k=1}^n \frac{1}{2k+\alpha} \\ = (1+\alpha) \prod_{k=2}^n (2k-1+\alpha) \prod_{k=1}^n \frac{1}{2k+\alpha}.$$

We may apply partial fractions by residues to the two products (degree of numerator is less than degree of denominator and poles are all simple) for the variable $$\alpha$$ and get

$$(1+\alpha) \sum_{k=1}^n \frac{1}{2k+\alpha} \mathrm{Res}_{\alpha=-2k} \prod_{q=2}^n (2q-1+\alpha) \prod_{q=1}^n \frac{1}{2q+\alpha} \\ = (1+\alpha) \sum_{k=1}^n \frac{1}{2k+\alpha} \prod_{q=2}^n (2q-1-2k) \prod_{q=1}^{k-1} \frac{1}{2q-2k} \prod_{q=k+1}^{n} \frac{1}{2q-2k} \\ = \frac{1}{2^{n-1}} (1+\alpha) \sum_{k=1}^n \frac{1}{2k+\alpha} \prod_{q=2}^n (2q-1-2k) \prod_{q=1}^{k-1} \frac{1}{q-k} \prod_{q=k+1}^{n} \frac{1}{q-k} \\ = \frac{1}{2^{n-1}} (1+\alpha) \sum_{k=1}^n \frac{1}{2k+\alpha} \frac{(-1)^{k-1}}{(k-1)!} \frac{1}{(n-k)!} \prod_{q=2}^n (2q-1-2k).$$

For the remaining product we get

$$\prod_{q=2}^n (2q-1-2k) = \prod_{q=2}^k (2q-1-2k) \prod_{q=k+1}^n (2q-1-2k) \\ = \frac{(-1)^{k-1} (2k-2)!}{(k-1)! \times 2^{k-1}} \prod_{q=1}^{n-k} (2q-1) \\ = \frac{(-1)^{k-1} (2k-2)!}{(k-1)! \times 2^{k-1}} \frac{(2n-2k)!}{(n-k)! \times 2^{n-k}}.$$

Collecting everything we have for the partial fraction decomposition

$$\frac{1}{2^{n-1}} (1+\alpha) \sum_{k=1}^n \frac{1}{2k+\alpha} \frac{(-1)^{k-1}}{(k-1)!} \frac{1}{(n-k)!} \frac{(-1)^{k-1} (2k-2)!}{(k-1)! \times 2^{k-1}} \frac{(2n-2k)!}{(n-k)! \times 2^{n-k}}$$

which is

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{4^{n-1}} (1+\alpha) \sum_{k=1}^n \frac{1}{2k+\alpha} {2k-2\choose k-1} {2n-2k\choose n-k}.}$$

Next to conclude we extract the coefficient on $$[\alpha^q]$$ and show that the RHS and the LHS yield the same, proving the claim (no pole at $$\alpha=0$$). We get for $$q=0$$ that we must have

$$\frac{1}{4^n} {2n\choose n} = \frac{1}{4^{n-1}} \sum_{k=1}^n \frac{1}{2k} {2k-2\choose k-1} {2n-2k\choose n-k} \\ = \frac{1}{2^{2n-1}} \sum_{k=0}^{n-1} \frac{1}{k+1} {2k\choose k} {2n-2-2k\choose n-1-k}.$$

We recognize Catalan numbers with OGF

$$C(z) = \frac{1-\sqrt{1-4z}}{2z}.$$

Continuing,

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

Now when $$k\gt n-1$$ there is no contribution to the coefficient extractor and we continue with

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

We have equality for $$q=0.$$ For $$q\ge 1$$ we must have that

$$\frac{1}{4^n} \sum_{k=1}^n {2k\choose k} {2n-2k\choose n-k} [\alpha^{q-1}] \frac{1}{2k} \frac{1}{1+\alpha/2/k} \\ = \frac{1}{4^n} \sum_{k=1}^n {2k\choose k} {2n-2k\choose n-k} (-1)^{q-1} \frac{1}{2^qk^q}$$

is the same as

$$\frac{1}{4^{n-1}} \sum_{k=1}^n ([\alpha^q] + [\alpha^{q-1}]) \frac{1}{2k+\alpha} {2k-2\choose k-1} {2n-2k\choose n-k}.$$

This is

$$\frac{1}{4^{n-1}} \sum_{k=1}^n \left((-1)^q \frac{1}{2^{q+1} k^{q+1}} + (-1)^{q-1}\frac{1}{2^qk^q}\right) {2k-2\choose k-1} {2n-2k\choose n-k} \\ = \frac{1}{4^{n-1}} \sum_{k=1}^n \left(-\frac{1}{2k} + 1\right) (-1)^{q-1}\frac{1}{2^qk^q} {2k-2\choose k-1} {2n-2k\choose n-k} \\ = \frac{1}{2^{2n-2}} \sum_{k=1}^n \frac{2k-1}{2k} (-1)^{q-1}\frac{1}{2^qk^q} \frac{k}{2k-1} {2k-1\choose k} {2n-2k\choose n-k} \\ = \frac{1}{2^{2n-1}} \sum_{k=1}^n (-1)^{q-1}\frac{1}{2^qk^q} {2k-1\choose k-1} {2n-2k\choose n-k} \\ = \frac{1}{2^{2n-1}} \sum_{k=1}^n (-1)^{q-1}\frac{1}{2^qk^q} \frac{k}{2k} {2k\choose k} {2n-2k\choose n-k} \\ = \frac{1}{4^n} \sum_{k=1}^n (-1)^{q-1}\frac{1}{2^qk^q} {2k\choose k} {2n-2k\choose n-k}.$$

We again have equality. This concludes the proof.

• Thank you very much for your hard work ! – Harmonic Sun Sep 20 '18 at 18:41
• Thank you. It will be interesting to see what other contributions appear regarding this challenging identity. – Marko Riedel Sep 20 '18 at 18:45
• Actually, yesterday I found myself another lead that might provide a possibily quickier proof, relying more heavily on generating functions. I will write it down here when complete. – Harmonic Sun Sep 20 '18 at 18:48
• @MarkoRiedel: Very nice solution. It is interesting that the residual approach does not directly lead to the wanted sum. This all is worth a some more detailed analysis. Thanks for this inspiring contribution. (+1) – Markus Scheuer Sep 21 '18 at 6:21
• Thanks to you as well. I tried the usual residue technique for quite some time before seeing that it would not work here, at least as far as I was able to verify. – Marko Riedel Sep 21 '18 at 12:00

This is a mere supplement to @MarkoRiedels answer. Mimicking his solution with a slight change we can simplify the proof.

We start with OP's left-hand side and obtain \begin{align*} \color{blue}{\prod_{k=1}^n}&\color{blue}{\left(1-\frac{1}{2k+\alpha}\right)}\\ &=\prod_{k=1}^n\frac{2k-1+\alpha}{2k+\alpha}\\ &=\alpha\prod_{k=1}^n(2k-1+\alpha)\prod_{k=0}^n\frac{1}{2k+\alpha}\tag{1}\\ &=\alpha\sum_{k=0}^n\frac{1}{2k+\alpha}\mathrm{Res}_{\alpha=-2k}\prod_{q=1}^n(2q-1+\alpha)\prod_{q=0}^n\frac{1}{2q+\alpha}\\ &=\alpha\sum_{k=0}^n\frac{1}{2k+\alpha}\prod_{q=1}^n(2q-1-2k)\prod_{q=0}^{k-1}\frac{1}{2q-2k}\prod_{q=k+1}^n\frac{1}{2q-2k}\\ &=\frac{\alpha}{2^n}\sum_{k=0}^n\frac{1}{2k+\alpha}(-1)^k\prod_{q=1}^k(2k+1-2q)\prod_{q=k+1}^n(2q-1-2k)\\ &\qquad\qquad\cdot\prod_{q=0}^{k-1}\frac{1}{q-k}\prod_{q=k+1}\frac{1}{q-k}\\ &=\frac{\alpha}{2^n}\sum_{k=0}^n\frac{1}{2k+\alpha}(-1)^k(2k-1)!!(2n-1-2k)!!\cdot\frac{1}{(-1)^kk!}\cdot\frac{1}{(n-k)!}\\ &=\frac{\alpha}{2^n}\sum_{k=0}^n\frac{1}{2k+\alpha}\cdot\frac{(2k)!}{2^kk!}\cdot\frac{(2n-2k)!}{2^{n-k}(n-k)!}\cdot\frac{1}{(-1)^kk!}\cdot\frac{1}{(n-k)!}\\ &=\frac{\alpha}{4^n}\binom{2n}{n}\sum_{k=0}^n\frac{1}{2k+\alpha}\cdot\frac{n!}{k!(n-k)!}\cdot\frac{n!}{k!(n-k)!}\cdot\frac{(2k)!(2n-2k)!}{(2n)!}\\ &\,\,\color{blue}{=\frac{\alpha}{4^n}\binom{2n}{n}\sum_{k=0}^n\binom{n}{k}^2\binom{2n}{2k}^{-1}\frac{1}{2k+\alpha}} \end{align*}

and the claim follows.

Comment:

• In (1) is the slight difference. Instead of factoring out $$1+\alpha$$ we multiply with $$\frac{\alpha}{\alpha}$$.
• +1 for having short enough lines for my browser. – J.G. Sep 22 '18 at 6:53
• @J.G.: Thanks. I also have to cope sometimes with this bothering aspect and I know from experience that a proper layout is helpful to provide information. – Markus Scheuer Sep 22 '18 at 7:29
• (+1). This is clearly the better proof. Not having seen your initial manipulation (what you call the slight change) proved costly later on. Let it be a lesson to the reader. – Marko Riedel Sep 22 '18 at 12:01
• @MarkoRiedel: Many thanks for your generous comment. – Markus Scheuer Sep 22 '18 at 12:05
• @J.G. $\texttt{MSE}$ added recently a column to the left ( $\texttt{Home, Questions,...,Unanswered}$ ). It killed a lot of space for the answers. That was a bad design. Those links must be at the top as it was sometimes ago – Felix Marin Oct 12 '18 at 23:26