# Prove or disprove ${{2a-1\choose a} + {2a-3\choose a-1} + {2a-5\choose a-2} + \dots {1\choose 1}}={2a\choose a+1}$

Prove or disprove $\displaystyle{{2a-1\choose a} + {2a-3\choose a-1} + {2a-5\choose a-2} + \dots {1\choose 1}}={2a\choose a+1}$

This is not homework. I'm trying to prove something related to Catalan numbers, and I'm stuck here.

I tried this: this is the coefficient of $x^a$ in $\displaystyle{(1+x)^{2a-1}+x(1+x)^{2a-3}+\dots x^{a-1}(1+x)}$

If we take $(1+x)^{2a-1}$ as the first term, then this is a geometric series of $a$ terms with $\displaystyle{\frac{x}{(1+x)^2}}$ as the common factor. Applying the formula for the summation of a geometric series, we get $$\displaystyle{\frac{(1+x)^{2a-1}[\displaystyle{\frac{x^a}{(1+x)^{2a}}}-1]}{\displaystyle{\frac{x}{(1+x)^2}-1}}}$$

On solving this, we get $$\displaystyle{[(1+x)^{2a+1}-x^a(1+x)](1+x+x^2)^{-1}}$$ $$\displaystyle{=[(1+x)^{2a+1}-x^a(1+x)][1-x(1+x)+x^2 (1+x)^2 -x^3 (1+x)^3\dots]}$$

Finding the coefficient of $x^a$ in this expression seems to be the sum of mutiple expressions again!

EDIT: Potato has shown that this is fase by substituting $a=3$. Could someone then give the general expression of the sum?

• Take $a=3$. $\textbf{}$ Jun 24, 2013 at 4:31
• (5 choose 3) + (3 choose 2) + 1 - (6 choose 4) = -1 Jun 24, 2013 at 4:32
• @Potato- by that substitution, I am getting ${5 \choose 3}+{3\choose 2}+{1\choose 1}={6\choose 4}-1$. Is that likely to be the general expression?
– user67803
Jun 24, 2013 at 4:36
• If you check out math world's article on Catalan numbers, there are a bunch of formulas there that might help you find what you want/need. Jun 24, 2013 at 4:44
• The LHS of the expression in the problem is equal to $\frac {1} {2} \sum_{k = 0}^{a - 1} {2a - 2k \choose a - k}$. All I can do is to loosely bound this sum from below and above, such as following: $\frac {3 ^ a - 1} {2} < \frac {1} {2} \sum_{k = 0}^{a - 1} {2a - 2k \choose a - k} < \frac {4 ^ a - 1} {3}$.
– user98213
Oct 2, 2013 at 11:13

You are looking for $\sum_{k=1}^n\binom{2k-1}k=\frac12\sum_{k=1}^n\binom{2k}k=-\frac12+\frac12\sum_{k=0}^n\binom{2k}k$. The expression in the summation is OEIS A006134, and has generating function $(1-X)\sqrt{1-4X}$. No closed form for the general term of this series appears to be known, so it is unlikely there is one for your problem.
This is false. You can see this by testing $a=3$.
$${ 5 \choose 3} + { 3 \choose 2 } + 1 = {6 \choose 4}-1\neq {6 \choose 4}$$
• Thanks. Is $\displaystyle{{2a-1\choose a} + {2a-3\choose a-1} + {2a-5\choose a-2} + \dots {1\choose 1}}={2a\choose a+1}-1$ likely to be the general expression then? Thanks!
• @AyushKhaitan I don't think so. More testing shows there doesn't seem to be a relation between the sides. You have two polynomials of the same degree in $a$, and there's really not much more you can say. Jun 24, 2013 at 4:38