3
$\begingroup$

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?

Thanks in advance!

$\endgroup$
5
  • 1
    $\begingroup$ Take $a=3$. $\textbf{}$ $\endgroup$
    – Potato
    Jun 24, 2013 at 4:31
  • $\begingroup$ (5 choose 3) + (3 choose 2) + 1 - (6 choose 4) = -1 $\endgroup$
    – Potato
    Jun 24, 2013 at 4:32
  • $\begingroup$ @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? $\endgroup$
    – user67803
    Jun 24, 2013 at 4:36
  • $\begingroup$ 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. $\endgroup$
    – Calvin Lin
    Jun 24, 2013 at 4:44
  • $\begingroup$ 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}$. $\endgroup$
    – user98213
    Oct 2, 2013 at 11:13

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – user67803
    Jun 24, 2013 at 4:37
  • $\begingroup$ @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. $\endgroup$
    – Potato
    Jun 24, 2013 at 4:38

You must log in to answer this question.