# Approaching Tricky Combinatorial Proofs - Tough Example

I'm struggling with finding effective ways to approach questions (especially proofs) that use summations and Taylor Series. I've worked through several simpler examples, but always get stuck once a non-trivial question arises. In particular, I'm hoping to get some help in proving the following statement $$\sum_{i=0}^{n-1} {2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}=2(1-\frac{1}{2^{2i}}{2i \choose i})$$

As a hint, it's stated that $\frac{1-\sqrt{1-x}}{\frac{1}{2}x}=\sum_{i=0}^{\infty}{2i \choose i}\frac{1}{i+1}\frac{x^{i}}{2^{2i}}$ and that it may potentially be necessary to derive the Taylor seires centered at $x=0$ for $\frac{1-\sqrt{1-x}}{x}$ and $\frac{1}{\sqrt{1-x}}$

With some help, I've done the following work, but am not sure if I'm either headed in the right direction, or even correct:

$$\sum_{i=0}^{n-1} {2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}=\sum_{i=0}^{\infty}{2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}-\sum_{i=n}^{\infty}{2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}=2-\sum_{i=n}^{\infty}{2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}$$ From here, I've tried to get to the point of proving the following: $$2-\sum_{i=n}^{\infty}{2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}=2-\frac{2}{2^n}{2n \choose n}$$ $$\sum_{i=n}^{\infty}{2i \choose i} \frac{1}{i+1}\frac{1}{2^{2i}}=\frac{2}{2^n}{2n \choose n}$$ I really don't know where to proceed next, or which direction the proof will continue in. Any additions/corrections would be greatly appreciated. Thank you!

Edit: to add on another potential solution, would it hold any water to try to write down a recurrence relation, assuming the left side of the first equation to be $a_n$?

• Consider the general Taylor series expansion $$f(x)=\sum_{k\ge 0} f_kx^k$$ then since $$(1-x)^{-1}=\sum_{l\ge 0}x^l$$ multiplying gives the series of partial sums of $f_k$: $$(1-x)^{-1}f(x)=\sum_{n\ge 0}\left(\sum_{k=0}^{n}f_k\right)x^n$$ You could try calling $f(x)=2(1-\sqrt{1-x})/x$ then multiplying by $(1-x)^{-1}$ to give $2x^{-1}(1-x)^{-1} - 2x^{-1}(1-x)^{-1/2}$ then expanding these as Taylor series about $x=0$ then equate coefficients of $x^{n-1}$. – N. Shales Mar 23 '17 at 0:11

We are interested in verifying that

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

Now we recognize the Catalan numbers here where

$$C(z) = \sum_{q\ge 0} {2q\choose q}\frac{1}{q+1} z^q = \frac{1-\sqrt{1-4z}}{2z}.$$

We then have from first principles that the sum is given by

$$S_n = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} C(z/4)\; dz.$$

Now recall the functional equation (e.g. from combinatorial species) of $C(z)$ which is

$$C(z) = 1 + z C(z)^2$$

which means that with $D(z) = C(z/4)$ we obtain

$$D(z) = 1 + z D(z)^2/4.$$

Recall that our integral is

$$S_n = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} D(z)\; dz.$$

We have that $$z = \frac{4D(z) - 4}{D(z)^2} = 4\frac{1}{D(z)} - 4\frac{1}{D(z)^2}$$

so in putting $w=D(z)$ we get

$$dz = \left(-4\frac{1}{w^2} + 8\frac{1}{w^3} \right) \; dw$$

which yields for the integral (we have $D(0) = 1$ as can be seen from the series)

$$S_n = \frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{w^{2n+2}}{4^{n+1} (w-1)^{n+1}} \frac{1}{1-4/w+4/w^2} \\ \times w \left(-4\frac{1}{w^2} + 8\frac{1}{w^3} \right) \; dw \\ = \frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{w^{2n+5}}{4^{n+1} (w-1)^{n+1}} \frac{1}{w^2-4w+4} \\ \times \left(-4\frac{1}{w^2} + 8\frac{1}{w^3} \right) \; dw \\ = \frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{w^{2n+2}}{4^{n+1} (w-1)^{n+1}} \frac{1}{(w-2)^2} \left(-4w + 8\right) \; dw \\ = \frac{1}{4^n} \frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{w^{2n+2}}{(w-1)^{n+1}} \frac{1}{1-(w-1)} \; dw.$$

The integral and the scalar in front are

$$\frac{1}{4^n} [(w-1)^{n}] \frac{1}{1-(w-1)} \sum_{q=0}^{2n+2} {2n+2\choose q} (w-1)^q \\ = \frac{1}{4^n} \sum_{q=0}^{n} {2n+2\choose q} [(w-1)^{n-q}] \frac{1}{1-(w-1)} = \frac{1}{2^{2n}} \sum_{q=0}^{n} {2n+2\choose q} \\ = \frac{1}{2^{2n+1}} \left(2^{2n+2} - {2n+2\choose n+1}\right).$$

where the last step was by inspection. We thus get for the closed form

$$\bbox[5px,border:2px solid #00A000]{ 2 - \frac{1}{2^{2n+1}} {2n+2\choose n+1}.}$$

Observe that this is

$$2 - \frac{1}{2^{2n+1}} \frac{2n+2}{n+1} {2n+1\choose n} = 2 - \frac{1}{2^{2n}} {2n+1\choose n} = 2 - \frac{1}{2^{2n}} {2n+1\choose n+1}$$

which is the form presented in the introduction. It would be interesting to see a formal power series only proof of this which would have to have certain features distinguishing it from the above, where we used the differential in the integral.

Remark. Induction is the simplest here, we get

$$2 - \frac{1}{2^{2n}} {2n+1\choose n+1} + {2n+2\choose n+1} \frac{1}{n+2}\frac{1}{2^{2n+2}} \\ = 2 - \frac{1}{2^{2n}} {2n+1\choose n+1} + {2n+3\choose n+2} \frac{1}{2n+3}\frac{1}{2^{2n+2}} \\ = 2 - \frac{1}{2^{2n}} {2n+2\choose n+2} \frac{n+2}{2n+2} + {2n+3\choose n+2} \frac{1}{2n+3}\frac{1}{2^{2n+2}} \\ = 2 - \frac{1}{2^{2n}} {2n+3\choose n+2} \frac{n+1}{2n+3} \frac{n+2}{2n+2} + {2n+3\choose n+2} \frac{1}{2n+3}\frac{1}{2^{2n+2}}.$$

Now

$$4 \frac{n+1}{2n+3} \frac{n+2}{2n+2} - \frac{1}{2n+3} = 1$$

and we obtain

$$2 - \frac{1}{2^{2n+2}} {2n+3\choose n+2}$$

which is the desired result. (Observe that $S_1 = 1 + \frac{1}{4} = 2 - \frac{1}{4} {3\choose 2}.$)

• THIS ^ Thank you, sir; I had just gone through it inductively before reading your remark, and got the same result. – tonimontana1389 Mar 23 '17 at 5:13
• @MarkoRiedel: Hi, Marko! Third approach added :-) (+1). – Markus Scheuer Mar 25 '17 at 7:46
• Thank you very much. Nice work in your answer. (+1). I did get to present a formal power series coefficient extractor that you might not have seen before. – Marko Riedel Mar 25 '17 at 21:20
• @MarkoRiedel: Yes, I see. Useful generalisation! :-) By the way, I've added this MSE post which might be of interest to you. – Markus Scheuer Mar 26 '17 at 16:40

Here is an approach based on the observation that \begin{align*} \sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{i+1}\cdot\frac{1}{2^{2i}} \end{align*} is a Cauchy-product which can be interpreted as the coefficient of the product of two (ordinary) generating functions. We recall the generating function of the Catalan numbers $C_i=\binom{2i}{i}\frac{1}{i+1}$ \begin{align*} C(x)=\sum_{i=0}^\infty C_i x^i=\frac{1-\sqrt{1-4x}}{2x}\tag{1} \end{align*} It is also convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain \begin{align*} \sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i}} &=\frac{1}{4^{n-1}}\sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{i+1}4^{n-1-i}\tag{2}\\ &=\frac{1}{4^{n-1}}[x^{n-1}]\frac{C(x)}{1-4x}\tag{3}\\ &=\frac{1}{4^{n-1}}[x^{n-1}]\frac{1-\sqrt{1-4x}}{2x(1-4x)}\tag{4}\\ &=\frac{1}{2\cdot4^{n-1}}[x^{n}]\left(\frac{1}{1-4x}-\frac{1}{\sqrt{1-4x}}\right)\tag{5}\\ &=\frac{1}{2\cdot4^{n-1}}\left(4^n-\binom{-\frac{1}{2}}{n}(-4)^n\right)\tag{6}\\ &=2\left(1-\frac{1}{2^{2n}}\binom{2n}{n}\right)\tag{7} \end{align*} and the claim follows.

Comment:

• In (2) we write the sum as Cauchy-product in the form $\sum_{i=0}^{n-1}a_ib_{n-1-i}$.

• In (3) we use the fact that the Cauchy-product is the coefficient of $x^{n-1}$ of $C(x)$ and the geometric series $\frac{1}{1-4x}$.

• In (4) we use the representation (1).

• In (5) we do a small rearrangement to easily derive the coefficients of the series and apply the rule $[x^{p+q}]A(x)=[x^p]x^{-q}A(x)$.

• In (6) we select the coefficient of $x^n$ of the geometric series and the binomial series with $\alpha=-\frac{1}{2}$.

• In (7) we apply the binomial identity \begin{align*} \binom{-\frac{1}{2}}{i}=\frac{1}{2^{2i}}\binom{2i}{i}(-1)^i \end{align*} See e.g. (1.9) in H.W. Goulds Binomial Identities, vol. 1.